WA 63分 #3 #8 #10 #11 求助
查看原帖
WA 63分 #3 #8 #10 #11 求助
367521
roger_yrj楼主2022/9/4 10:50
#include<bits/stdc++.h>
using namespace std;
int n,dfn[114514],low[114514],_n,tcnt,visi[114514],viso[114514],ansi,anso,belong[114514];
vector<int>e[114514];
stack<int>sta;
void tarjan(int u){
	dfn[u]=low[u]=++tcnt;
	sta.push(u);
	for(int i=0,len=e[u].size();i<len;i++){
		int v=e[u][i];
		if(!dfn[v])tarjan(v),low[u]=min(low[v],low[u]);
		else if(!belong[v])low[u]=min(low[v],low[u]);
	}
	if(low[u]==dfn[u]){
		_n++;
		while(sta.top()!=u){
			belong[sta.top()]=_n;
			sta.pop();
		}
		belong[u]=_n;
		sta.pop();
	}
}
int main(){
	cin>>n;
	for(int i=1,x;i<=n;i++){
		while(1){
			scanf("%d",&x);
			if(!x)break;
			e[i].push_back(x);
		}
	}
	for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
	for(int u=1;u<=_n;u++){
		for(int i=0,len=e[u].size();i<len;i++){
			int v=belong[e[u][i]];
			if(belong[u]!=v)visi[v]=1,viso[belong[u]]=1;
		}
	}
	for(int i=1;i<=_n;i++){
		if(!visi[i])ansi++;
		if(!viso[i])anso++;
	}
	if(_n==1)cout<<"1\n0"; 
	else cout<<ansi<<endl<<max(ansi,anso);
}
2022/9/4 10:50
加载中...