80分求助
查看原帖
80分求助
509923
SongShouqian楼主2022/6/8 21:41

WA 了最后两个点,应该是 tarjan 写错了,求大佬帮忙!

#include<bits/stdc++.h>
using namespace std;
const int N=10005,M=50005;
int n,m,head[N],cnt=0,dfn[N],low[N],st[N],top=0,deep,ans=0,color[N];
bool vis[N];
struct node{
	int to,last;
}e[M];
void add(int u,int v)//建边
{
	cnt++;
	e[cnt].to=v;
	e[cnt].last=head[u];
	head[u]=cnt;
}
void tarjan(int u)//求连通分量
{
	deep++;
	dfn[u]=deep;
	low[u]=deep;
	st[top]=u;
	vis[u]=1;
	top++;
	int v;
	for(int i=head[u];i;i=e[i].last)
	{
		v=e[i].to;
		if(dfn[v]==0)
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else
		{
			if(vis[u])
			{
				low[u]=min(low[u],low[v]);
			}
		}
	}
	if(dfn[u]==low[u])
	{
		ans++;
		while(st[top-1]!=u)
		{
			top--;
			vis[st[top]]=0;
			color[ans]++;
		}
		top--;
		vis[u]=0;
		color[ans]++;//color数[i]表示第i个强连通分量的大小
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	int u,v;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		add(u,v);//建单向边
	}
	for(int i=1;i<=n;i++)
	{
		if(dfn[i]==0)//如果这个点还没被遍历过就求
		{
			tarjan(i);
		}
	}
	int sum=0;
	for(int i=1;i<=ans;i++)
	{
		if(color[i]>1)
		{
			sum++;
		}
	}
	printf("%d",sum);
	return 0;
}
2022/6/8 21:41
加载中...