90分的代码(最后一个点WA了)

#include <bits/stdc++.h>
using namespace std;
const long long Max = 111111,Maxm = 555555;
struct e {
    long long nex,to;
} a[Maxm];
long long dfn[Max],low[Max],ans[Max],num,size[Max],head[Max],tot;
bool cut[Max];
long long n,m,rt;
void add(long long x,long long y) {
    a[++tot].to = y,a[tot].nex = head[x],head[x] = tot;
}
void tarjan(long long x) {
    dfn[x] = low[x] = ++num;
    size[x] = 1;
    long long flag = 0,sum = 0;
    for(long long i = head[x];i;i = a[i].nex) {
        long long y = a[i].to;
        if(!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x],low[y]);
            size[x] += size[y];
            if(low[y] >= dfn[x]) {
                sum += size[y];
                ans[x] += size[y] * (n - size[y]);
                flag++;
                if(x != rt || flag > 1) {
                    cut[x] = 1;
                }
            }
        } else {
            low[x] = min(low[x],dfn[y]);
        }
    }
    if(cut[x]) {
        ans[x] += (n - sum - 1) * (sum + 1) + (n - 1);
    } else {
        ans[x] = 2 * (n - 1);
    }
}

int main() {
    #ifndef ONLINE_JUDGE
    freopen("P3469.in","r",stdin);
    freopen("P3469.out","w",stdout);
    #endif
    cin >> n >> m;
    for(long long i = 1;i <= m;i++) {
        long long x,y;
        cin >> x >> y;
        if(x != y) {
            add(x,y),add(y,x);
        }
    }
    rt = 1;
    tarjan(1);
    // cout << dfn[2] << '\n';
    for(long long i = 1;i <= n;i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}

评测记录

AC的代码

#include <bits/stdc++.h>
using namespace std;
const long long Max = 111111,Maxm = 555555;
// struct e {
//     long long nex,to;
// } a[Maxm];
vector<int> v[Max];
long long dfn[Max],low[Max],ans[Max],num,size[Max],head[Max],tot;
bool cut[Max];
long long n,m,rt;
void add(long long x,long long y) {
    // a[++tot].to = y,a[tot].nex = head[x],head[x] = tot;
    v[x].push_back(y);
}
void tarjan(long long x) {
    dfn[x] = low[x] = ++num;
    size[x] = 1;
    long long flag = 0,sum = 0;
    for(int y : v[x]) {
        if(!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x],low[y]);
            size[x] += size[y];
            if(low[y] >= dfn[x]) {
                sum += size[y];
                ans[x] += size[y] * (n - size[y]);
                flag++;
                if(x != 1 || flag > 1) {
                    cut[x] = 1;
                }
            }
        } else {
            low[x] = min(low[x],dfn[y]);
        }
    }
    if(cut[x]) {
        ans[x] += (n - sum - 1) * (sum + 1) + (n - 1);
    } else {
        ans[x] = 2 * (n - 1);
    }
}

int main() {
    #ifndef ONLINE_JUDGE
    freopen("P3469.in","r",stdin);
    freopen("P3469.out","w",stdout);
    #endif
    cin >> n >> m;
    for(long long i = 1;i <= m;i++) {
        long long x,y;
        cin >> x >> y;
        if(x != y) {
            add(x,y),add(y,x);
        }
    }
    tarjan(1);
    for(long long i = 1;i <= n;i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}

评测记录

这两个代码只有边的存储方式不同。