全T求调
查看原帖
全T求调
580412
wenxiaoyang楼主2024/4/9 19:50
#include<bits/stdc++.h>
using namespace std;
const int maxn=100001;
int n,m,tot,top,num,cnt,ans,ccnt;
int low[maxn],dfn[maxn],sta[maxn],belong[maxn],head[maxn];
bool instack[maxn];
struct _{
	int from,next,to;
}e[maxn];
void add(int u,int v)
{
	e[++tot].from=u;
	e[tot].to=v;
	e[tot].next=head[u];
	head[u]=tot;
}
void tanjan(int x)
{
	dfn[x]=low[x]=++num;
	sta[++top]=x;instack[x]=1;
	for(int i=head[x];i;e[i].next)
	{
		int y=e[i].to;
		if(!dfn[y])
		{
			tanjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(instack[y])
			low[x]=min(low[x],dfn[y]);
	}
	if(low[x]==dfn[x])
	{
		cnt++;
		ccnt=0;
		int y;
		do
		{
			ccnt++;
			y=sta[top--];
			belong[y]=cnt;
			instack[y]=0;
		}while(x!=y);
		if(ccnt>1)ans++;
	}
}
int main()
{
	cin>>n>>m;
	int u,v;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v;
		add(u,v);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])
			tanjan(i);
	}
	cout<<ans;
	return 0;
}
2024/4/9 19:50
加载中...