tarjan模板只有50分,求助
查看原帖
tarjan模板只有50分,求助
61737
z1212楼主2021/4/11 17:16
#include<bits/stdc++.h>
using namespace std;
const int m1=1e4+5;
const int m2=5e4+5; 
struct edge{
	int v,n;
}e[m2];
int n,m,t,h[m1],dfn[m1],low[m1],tt,st[m1],top,v,co[m1],col,ans,xx,yy,o;
void add(int x,int y){
	t++;
	e[t].n=h[x];
	e[t].v=y;
	h[x]=t;
}
void tarjan(int x){
	dfn[x]=low[x]=++tt;
	st[++top]=x;
	for(int i=h[x];i;i=e[i].n){
		v=e[i].v;
		if(!dfn[v]){
			tarjan(v);
			low[x]=min(low[x],low[v]);			
		}else if(!co[v])low[x]=min(low[x],dfn[v]);
	}
	if(dfn[x]==low[x]){
	//	if(top>=2)ans++;
		col++;
		co[x]=col;
		while(st[top]!=x){
			co[st[top]]=col;
			top--;
			o++;
		}
		top--;
		o++;
		if(o>=2)ans++;
		o=0;
	}
}
int main()
{
	freopen("P2863_2.in","r",stdin); 
	freopen("1.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&xx,&yy);
		add(xx,yy);
	}
	for(int i=1;i<=n;i++)
	if(!dfn[i])tarjan(i);
	cout<<ans;
	return 0;
}
2021/4/11 17:16
加载中...