求调
查看原帖
求调
741720
__Mkigita__楼主2023/7/10 08:41

rt

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int>t[300],tf[300],nt[300];
int n,visz[300],visf[300],nums,out[300],cnt,color[300],visn[300],cd[300],tmd[300];
void dfs1(int x){
	visz[x]=1;
	for(int i=0;i<t[x].size();i++){
		if(visz[t[x][i]]) continue;
		dfs1(t[x][i]);
	}
	out[++cnt]=x;
}
void dfs2(int x){
	color[x]=nums;
	visf[x]=1;
	for(int i=0;i<tf[x].size();i++){
		if(visf[tf[x][i]]) continue;
		dfs2(tf[x][i]);
	}
}
void kosaraju(){
	for(int i=1;i<=n;i++){
		if(visz[i]) continue;
		dfs1(i);
	}
	for(int i=1;i<=cnt;i++){
		if(visf[i]) continue;
		nums++;
		dfs2(i);
	}
}
void comeup(int x,int lc){
	visn[x]=1;
	for(int i=0;i<t[x].size();i++){
		if(visn[t[x][i]]) continue;
		if(color[t[x][i]]==lc) comeup(t[x][i],color[t[x][i]]);
		else{
			comeup(t[x][i],color[t[x][i]]);
			cd[t[x][i]]++;
		}
	}
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int opt;
		while(opt!=0){
			cin>>opt;
			t[i].push_back(opt);
			tf[opt].push_back(i);
		}
		opt=11514;
	}
	kosaraju();
	for(int i=n;i>=1;i--){
		comeup(1,color[1]);
	} 
	int ans=0;
	for(int i=1;i<=n;i++){
		if(cd[i]==0&&tmd[color[i]]==0){
			ans++;
			tmd[color[i]]=1;
		}
	}
	cout<<ans;
	return 0;
}
2023/7/10 08:41
加载中...