求大佬帮看看~~~
查看原帖
求大佬帮看看~~~
377876
lbc20070331楼主2022/7/3 20:53
#include<bits/stdc++.h>
using namespace std;
int n,pos,gid,cnt,g[10005],sz[10005],dfn[10005],low[10005],s[10005];
int last[10005],to[50005],pre[50005];
void tan(int now){
	dfn[now]=low[now]=++cnt;
	s[++pos]=now;
	for(int i=last[now];i!=0;i=pre[i]){
		int t=to[i];
		if(dfn[t]==0){
			tan(t);
			low[now]=min(low[now],low[t]);
		}
		if(g[t]==0){
			low[now]=min(low[now],dfn[t]);
		}
	}
	if(dfn[now]==low[now]){
		gid++;
		while(s[pos]!=now){
			g[s[pos]]=gid,sz[gid]++;
			pos--;
		}
		g[s[pos]]=gid,sz[gid]++;
		pos--;
	}
}
int main()
{
	cin>>n;
	int It=0;
	for(int i=1;i<=n;i++){
		int a;
		cin>>a;
		for(int j=1;j;j++){
			if(a==0){
				It++;
				break;
			}
			else{
				to[++It]=a;
				pre[It]=last[i];
				last[i]=It;
				cin>>a;
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(dfn[i]==0){
			tan(i);
		}
	}
	cout<<gid;
	return 0;
}
2022/7/3 20:53
加载中...