【題解】ZeroJudge e720: 108北二5.修哪條路?

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e720

#include <iostream>
#include <vector>
using namespace std;

int n, m, a, b, ans, idx, d[2005], l[2005], sz[2005], vis[2005];
vector <int> v[2005], e[2005];

void dfs(int x, int pre){
    idx++;
    d[x] = idx;
    l[x] = idx;
    sz[x] = 1;
    for (int i:v[x]){
        if (i == pre) continue;
        if (!d[i]){
            dfs(i, x);
            sz[x] += sz[i];
            l[x] = min(l[x], l[i]);
        }
        else{
            l[x] = min(l[x], d[i]);
        }
        if (d[x] < l[i]) e[x].push_back(i);
    }
}
void dfs2(int x, int pre){
    vis[x] = 1;
    for (int i:e[x]){
        ans = max(ans, sz[i]*(n-sz[i]));
    }
    for (int i:v[x]){
        if (!vis[i]) dfs2(i, x);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        cin >> a >> b;
        a++;
        b++;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1, 0);
    dfs2(1, 0);
    cout << ans << "\n";
}
分享本文 Share with friends