就是百度百科上的tarjan算法他把縮點什么的都總結(jié)好了。

/*
ID:jinbo wu
TASK:schlnet
LANG:C++
*/ 
#include<bits/stdc++.h>
using namespace std;
vector<int> g[110];
stack<int> s;
int x[110*100],y[110*100];
bool instack[110];
int belong[110],dfn[110],low[110];
int t=1,cnt;
int in[110],out[110];
void tarjan(int i)
{int j;dfn[i]=low[i]=t++;instack[i]=true;s.push(i);for(int e=0;e<g[i].size();e++){j=g[i][e];if(dfn[j]==0){tarjan(j);low[i]=min(low[j],low[i]);}else{if(instack[j]){low[i]=min(low[i],dfn[j]);}}}if(dfn[i]==low[i]){cnt++;do{j=s.top();s.pop();instack[j]=false;belong[j]=cnt;}while(j!=i);}}
int main()
{freopen("schlnet.in","r",stdin);freopen("schlnet.out","w",stdout);int n,v;cin>>n;int m=0;for(int i=1;i<=n;i++){while(cin>>v,v){g[i].push_back(v);x[m]=i;y[m++]=v;}}	for(int i=1;i<=n;i++){if(!dfn[i])tarjan(i);}for(int i=0;i<m;i++){int a=belong[x[i]];int b=belong[y[i]];if(a!=b){out[a]++;in[b]++;}}int ans1=0;int ans2=0;for(int i=1;i<=cnt;i++){if(out[i]==0)ans1++;if(in[i]==0)ans2++;}if(cnt==1){cout<<1<<endl<<0<<endl;}else{cout<<ans2<<endl<<max(ans1,ans2)<<endl;}
} 

總結(jié)

以上是生活随笔為你收集整理的usaco Network of Schools的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。