51nod 2877熟练使用tarjan的知识

我一开始想到tarjan 没想到咋做 看了题解直呼妙阿
考虑一个点有多个子块 若子块中的点不能回到父节点 那么这个子块 就和 其他子块是不能互相到达的
这时候只需要记录 已经遍历的多少子块即可 这样不会重复

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f

using namespace std;

const int N = 1e6 + 10,M = 5e5 + 10;
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;

int head[N],to[M * 2],last[M * 2],cnt;
void add(int a,int b){
    
    to[++cnt] = b;
    last[cnt] = head[a];
    head[a] = cnt;
}

int n,m;
ll dfn[N],low[N],times,sz[N],pn; ll ans[N];
void tarjan(int x){
    
    dfn[x] = low[x] = ++times;
    sz[x] = 1;
    ll pn = 0;
    for(int i = head[x]; i != -1; i = last[i]){
    
        int j = to[i];
        if(!dfn[j]){
    
            tarjan(j);
            sz[x] += sz[j];
            if(dfn[x] <= low[j]){
    
                ans[x] += sz[j] * pn;
                pn += sz[j];
            }
            low[x] = min(low[x],low[j]);
        }else low[x] = min(low[x],dfn[j]);
    }

    ans[x] += pn * (n - pn - 1);
}

int main(){
    
    memset(head,-1,sizeof head);
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
    
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }

    tarjan(1);

    for(int i = 1; i <= n; i++){
    
        cout << (ans[i] + n - 1) * 2 << endl;
    }



    return 0;
}