有人吗?蒟蒻求助80,求助,好心人是你吗?
查看原帖
有人吗?蒟蒻求助80,求助,好心人是你吗?
191993
six_小6猪楼主2021/2/9 21:46
#include<iostream>
#include<cstdio>
using namespace std;
struct edge
{
	int to;
	int nxt;
}e[4*5000100];
int n,m;
int head[1000003];
long long ans[1000003];
int size[1000003];
int cnt;
void add(int from,int to)
{
	e[++cnt].to=to;
	e[cnt].nxt=head[from];
	head[from]=cnt;
}
int dfn[1000003],low[1000003];
int cut[1000003];
int tim;
void tarjan(int x,int fa)
{
	size[x]=1;
	dfn[x]=low[x]=++tim;
	int ch=0;
	int sum=0;
	for(int i=head[x];i;i=e[i].nxt)
	  {
	  	int y=e[i].to;
	  	if(!dfn[y])
	  	{
	  		tarjan(y,fa);
	  		size[x]+=size[y];
	  		low[x]=min(low[x],low[y]);
	  		if(low[y]>=dfn[x]&&x!=fa)
	  		{
	  			ans[x]+=(long long)size[y]*(n-size[y]);
	  			sum+=size[y];
	  			cut[x]=1;

			  }
	  		if(x==fa) 
			  ch++;
		  }
		  else
		    low[x]=min(dfn[y],low[x]);
	  }
	  if(ch>=2&&x==fa)
	    cut[x]=1;
	if(cut[x]==0)
	  ans[x]=2*(n-1);
	else ans[x]+=(long long)(n-sum-1)*(sum+1)+(n-1);
}
int main()
{
	//freopen("P3469_1.in","r",stdin);
	//freopen("P3469_1.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			tarjan(i,-1);
	for(int i=1;i<=n;i++)
	  printf("%d\n",ans[i]);
	fclose(stdin);
	fclose(stdout);
}
2021/2/9 21:46
加载中...