Tarjan模板,10分,T了90分,求助
查看原帖
Tarjan模板,10分,T了90分,求助
344382
lmrttx楼主2021/1/3 08:17

RT,谢谢

#include<bits/stdc++.h>
using namespace std;
#define N 10001 
#define M 50001
int ver[M],nxt[M],head[M],dfn[N],low[N],sta[N],ins[N],c[N];
int n,m,tot,num,top,cnt;
int scc[N];
void add(int x,int y){ver[++tot]=y;nxt[tot]=head[x];head[x]=tot;}
void Tarjan(int x){
	dfn[x]=low[x]=++num;
	sta[++top]=x;ins[x]=1;
	for(int i=head[x];i;i=nxt[x])if(!dfn[ver[i]]){
		Tarjan(ver[i]);low[x]=min(low[x],low[ver[i]]);
	}else if(ins[ver[i]])low[x]=min(low[x],dfn[ver[i]]);
	if(dfn[x]==low[x]){
		cnt++;int y;
		do{
			y=sta[top--],ins[y]=0;
			c[y]=cnt;
			scc[cnt]++;
		}while(x!=y);
	}
} 
int rp;
int main(){
	scanf("%d%d",&n,&m);for(register int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),add(x,y);
	for(register int i=1;i<=n;i++)if(!dfn[i])Tarjan(i);
	for(register int i=1;i<=cnt;i++)if(scc[i]>1)rp++;
	printf("%d",rp);return 0;
} 
2021/1/3 08:17
加载中...