比赛 4043级NOIP2022欢乐赛6th 评测结果 WAAAEAAAAWAAEAAAAAAA
题目名称 BLO-Blockade 最终得分 80
用户昵称 ZRQ 运行时间 0.614 s
代码语言 C++ 内存使用 4.21 MiB
提交时间 2022-11-18 20:00:20
显示代码纯文本
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100005,M=500005;
int n,m,hd[N],e[M],nt[M],idx,df[N],lw[N],clk,siz[N];
ll ans[N];
char ch;
inline void add(int x,int y){nt[++idx]=hd[x],hd[x]=idx,e[idx]=y;}
inline void read(int &x){x=0;ch=getchar();while(ch<48||ch>57)ch=getchar();while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return ;}
void tarjan(int cur)
{
	int res=0;
	siz[cur]=1;
	df[cur]=lw[cur]=++clk;
	for(int i=hd[cur];i;i=nt[i])
	{
		if(!df[e[i]])
		{
			tarjan(e[i]);
			siz[cur]+=siz[e[i]];
			lw[cur]=min(lw[cur],lw[e[i]]);
			if(lw[e[i]]>=df[cur]) ans[cur]+=siz[e[i]]*res,res+=siz[e[i]];
		}
		lw[cur]=min(lw[cur],df[e[i]]);
	}
	ans[cur]+=(n-res-1)*res;
	return ;
}
int main()
{
	freopen("BLO.in","r",stdin);
	freopen("BLO.out","w",stdout);
	read(n),read(m);
	for(int i=1,x,y;i<=m;++i) read(x),read(y),add(x,y),add(y,x);
	for(int i=1;i<=n;++i) if(!df[i]) tarjan(i);
	for(int i=1;i<=n;++i) printf("%lld\n",(ans[i]+n-1)<<1);
	return 0;
}