第一次写Tarjan求调
查看原帖
第一次写Tarjan求调
794148
cyx20091026楼主2025/1/4 21:32
#include<bits/stdc++.h>
using namespace std;
struct EDGE{
	int to,nxt;
}edge[10001];
stack<int> s;
int n;
int ans,num,cnt;
int belong[10001],low[10001],dfn[10001],degree[10001];
bool ins[10001];
int tot=0;
int head[10001];
void add(int u,int v){
	tot++;
	edge[tot].to=v;
	edge[tot].nxt=head[u];
	head[u]=tot;
}
void tarjan(int u){
	low[u]=dfn[u]=++cnt;
	s.push(u);ins[u]=true;
	for(int i=head[u];i!=-1;i=edge[i].nxt){
		int v=edge[i].to;
		if(!dfn[v]){
			
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(ins[v]){
			low[u]=min(low[u],low[v]);
		}
	}
	if(dfn[u]==low[u]){
		int v;
		num++;
		do{
			v=s.top();
			s.pop();
			ins[v]=false;
			belong[v]=num;
		}while(v!=u);
	}
}
int main(){
	cin>>n;
	memset(head,-1,sizeof(head));
	for(int u=1;u<=n;u++){
		int v;
		while(true){
			cin>>v;
			if(!v) break;
			add(u,v);
		}
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tarjan(i);			
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=head[i];j!=-1;j=edge[j].nxt){
			int to=edge[j].to;
			if(belong[i]!=belong[j]){
				degree[belong[j]]++;
			}
		}
	}
	for(int i=1;i<=num;i++){
		if(degree[i]==0) ans++;
	}
	cout<<ans;
	return 0;
}
2025/1/4 21:32
加载中...