tarjan求割点，乘法原理统计答案，对数答案翻倍。

By：大奕哥

1 #include
     
       2 using namespace std; 3 const int N=100005; 4 struct node{ 5     int to,nex; 6 }e[1000005]; 7 int head[N],dfn[N],low[N],size[N],idx,cnt,n,m; 8 long long ans[N]; 9 void add(int x,int y)10 {11     e[++cnt].to=y;e[cnt].nex=head[x];head[x]=cnt;12 }13 void dfs(int x,int fa)14 {15     dfn[x]=low[x]=++idx;size[x]=1;int num=0;16     for(int i=head[x];i;i=e[i].nex)17     {18         int y=e[i].to;19         if(y==fa)continue;20         if(!dfn[y])21         {22             dfs(y,x);23             size[x]+=size[y];24             low[x]=min(low[x],low[y]);25             if(low[y]>=dfn[x])26             {27                 ans[x]+=1ll*num*size[y];28                 num+=size[y];29             }30         }31         else if(size[y])low[x]=min(low[x],dfn[y]);32     }33     ans[x]+=1ll*num*(n-num-1);ans[x]+=n-1;34 }35 int main()36 {37     scanf("%d%d",&n,&m);38     for(int i=1;i<=m;++i)39     {40         int x,y;41         scanf("%d%d",&x,&y);42         add(x,y);add(y,x);43     }44     for(int i=1;i<=n;++i)45     if(!dfn[i])dfs(i,i);46     for(int i=1;i<=n;++i)47     printf("%lld\n",ans[i]*2);48     return 0;49 }