Tarjan TLE !??
查看原帖
Tarjan TLE !??
54372
A_Đark_Horcrux楼主2020/10/16 22:14

20pts 我哪里写假了qaq

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=5e4+10;
inline int read()
{
	int s=0,b=1; char c=getchar();
	while(c<'0'||c>'9') {if (c=='-') b=-1; c=getchar();}
	while(c>='0'&&c<='9') s=s*10+c-'0',c=getchar();
	return s*b;
}
struct edge
{
	int from,to,next;
}a[N];
int n,m,t,x,y,cnt,top,ans,c,i,j;
int s[N],h[N],dfn[N],low[N],vis[N],color[N],in[N],tot[N];
void build(int x,int y)
{
	a[++t].from=h[x]; a[t].to=y; a[t].next=h[x];
	h[x]=t; return ;
}
void tarjan(int now)
{
	dfn[now]=low[now]=++cnt;
	s[++top]=now; vis[now]=1;
	for(int j=h[now];j!=-1;j=a[now].next)
	{
		int u=a[j].to;
		if(!dfn[u])
			tarjan(u),low[now]=min(low[now],low[u]);
		else if(vis[u])
			low[now]=min(low[now],dfn[u]);
	}
	if(dfn[now]==low[now])
	{
		int cur; c++;
		do
		{
			cur=s[top--];
			vis[cur]=0; color[cur]=c; tot[c]++; 
		} 
		while(now!=cur);
	}
	return ;
}
int main()
{
	n=read(),m=read();
	for(i=0;i<=N;i++) h[i]=-1;
	for(i=1;i<=m;i++) x=read(),y=read(),build(x,y);
	for(i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
	for(i=1;i<=n;i++)
		for(j=h[i];j!=-1;j=a[i].next)
			if(color[i]!=color[a[j].to]) in[color[i]]++;
	for(i=1;i<=c;i++)
		if(in[i]==0)
		{ 
			if(ans) return !puts("0");
			else ans=i;
		}
	printf("%d",tot[ans]);
	return 0;
}

2020/10/16 22:14
加载中...