36分求助,不知道Tarjan那里错了,悬赏关注,谢谢!
查看原帖
36分求助,不知道Tarjan那里错了,悬赏关注,谢谢!
546681
lcbridgeAK CSP-S楼主2023/4/3 19:15
#include <bits/stdc++.h>
using namespace std;
const int MAXN=105;
int n,dfn[MAXN],low[MAXN],cnt,scc[MAXN],G[MAXN][3],ans,outd[MAXN],ind[MAXN];
vector <int> g[MAXN];
bool vis[MAXN];
stack <int> s;
void tarjan(int u){
	dfn[u]=low[u]=++cnt;
	s.push(u);
	vis[u]=1;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(!scc[v])low[u]=min(low[u],dfn[u]);
	}
	if(dfn[u]==low[u]){
		ans++;
		int v;
		do{
			v=s.top();
			s.pop();
			vis[v]=0;
			scc[v]=ans;
		}while(u!=v);
	}
}
int main(){
	int tmp=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int x;
		while(true){
			scanf("%d",&x);
			if(!x)break;
			g[i].push_back(x);
		}
	}
	for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
	for(int i=1;i<=n;i++){
		for(int j=0;j<g[i].size();j++){
			int u=i;
			int v=g[i][j];
			if(scc[u]!=scc[v]){
				ind[scc[u]]++;
				outd[scc[v]]++;
			}
		}
	}
    int ans1=0,ans2=0;
    //cout<<ans<<endl;
    for(int i=1;i<=ans;i++){
		ans1+=(!ind[i]);
		ans2+=(!outd[i]);
	}
    printf("%d\n%d",ans1,max(ans1,ans2));
	return 0;
}

谢谢!

2023/4/3 19:15
加载中...