为什么直接加次数(shu)只有80分啊
查看原帖
为什么直接加次数(shu)只有80分啊
752711
hateful_bug楼主2024/6/6 19:26
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m,h[N],nx[N],b[N],tt,dfn[N],low[N],sjc,zhan[N],top,cnt;
bool pd[N];
void zj(int x,int y)
{
	b[++tt]=y;
	nx[tt]=h[x];
	h[x]=tt;
}
void tarjan(int x)
{
	dfn[x]=low[x]=++sjc;
	zhan[++top]=x;pd[x]=true;
	for(int i=h[x];i;i=nx[i])
	{
		int y=b[i];
		if(!dfn[y])
		{
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(pd[x])
		low[x]=min(low[x],dfn[y]);
	}
	if(low[x]==dfn[x])
	{
		int shu=0,z;
		do
		{
			z=zhan[top--];
			pd[z]=false;
			++shu;
		}while(z!=x);
		if(shu>1)
		++cnt;
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		zj(x,y);
	}
	for(int i=1;i<=n;i++)
	if(!dfn[i])
	tarjan(i);
	printf("%d",cnt);
	return 0;
}
2024/6/6 19:26
加载中...