蒟蒻求助啊啊啊啊,只有34分qaq
查看原帖
蒟蒻求助啊啊啊啊,只有34分qaq
362627
frank15楼主2021/3/1 19:51
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
const int maxn=110;
int n,V,num,tot,ans1,ans2;
int low[maxn],dfn[maxn];
int mark[maxn],in[maxn],out[maxn];
bool vis[maxn];
vector<int> v[maxn];
stack<int> st;
void dfs(int k){
	low[k]=dfn[k]=++num;
	vis[k]=1;
	st.push(k);
	for(int i=0;i<v[k].size();i++)
		if(!dfn[v[k][i]]){
			dfs(v[k][i]);
			low[k]=min(low[k],low[v[k][i]]);
		}
		else
			if(vis[k])
				low[k]=min(low[k],dfn[v[k][i]]);
	if(dfn[k]==low[k]){
		tot++;
		while(1){
			int TOP=st.top();
			st.pop();
			mark[TOP]=tot;
			vis[TOP]=0;
			if(TOP==k)
				break;
		}
	}
	return ;
}
void tarjan(){
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			dfs(i);
	return ;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;;j++){
			scanf("%d",&V);
			if(!V)
				break;
			v[i].push_back(V);
		}
	tarjan();
	for(int i=1;i<=n;i++)
		for(int j=0;j<v[i].size();j++)
			if(mark[i]!=mark[v[i][j]]){
				in[mark[v[i][j]]]++;
				out[mark[i]]++;
			}
	for(int i=1;i<=tot;i++){
		if(!in[i])
			ans1++;
		if(!out[i])
			ans2++;
	}
	cout<<ans1<<endl<<max(ans1,ans2);
	return 0;
}
2021/3/1 19:51
加载中...