易错点:
- 必须开long long.
- 边要开到2e6.
- 初始化dfn[x]时候需要一块初始化low[x].
- 输出时需要使用”%lld\n”.
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
const int MAXN=2e5,MAXM=2e6;
struct Edge{
int from,to,w,nxt;
}e[MAXM];
int head[MAXN],edgeCnt=1;
void addEdge(int u,int v,int w){
e[++edgeCnt].from=u;
e[edgeCnt].to=v;
e[edgeCnt].w=w;
e[edgeCnt].nxt=head[u];
head[u]=edgeCnt;
}
int dfn[MAXN],dfnCnt=0,low[MAXN],siz[MAXN];
bool cut[MAXN];
int s,n;
ll ans[MAXN];
void tarjan(int x){
dfn[x]=low[x]=++dfnCnt;
siz[x]=1;
int cutNum=0,sonSum=0;
for(int i=head[x];i;i=e[i].nxt){
int nowV=e[i].to;
if(!dfn[nowV]){
tarjan(nowV);
siz[x]+=siz[nowV];
low[x]=min(low[x],low[nowV]);
if(low[nowV]>=dfn[x]){
cutNum++;
if(x!=s||cutNum>1)cut[x]=1;
sonSum+=siz[nowV];
ans[x]+=(ll)siz[nowV]*(n-siz[nowV]);//son to others
}
}else low[x]=min(low[x],dfn[nowV]);
}
if(cut[x])ans[x]+=(ll)(n-(sonSum+1))*(sonSum+1)+(n-1);//others to us+me to others
else ans[x]=2*(n-1);//x to others
}
int main(){
int m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
addEdge(u,v,1);
addEdge(v,u,1);
}
s=1;
tarjan(s);
for(int i=1;i<=n;i++)
printf("%lld\n",ans[i]);
return 0;
}