本文主要是介绍poj 1236 Network of Schools （tarjan），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://poj.org/problem?id=1236
题意为给一个有向图
第一个问题是至少选择多少个点组成一个集合，然后把这个集合看成一个整体，从这个整体能够走到其他所有的点（除了这个整体）
第二个问题是添加多少边可成为完全连通图
tarjan缩点完成后，将每一个强连通分量看成一个点，然后处理这些“点”的出入度。
即可。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<stack>
using namespace std;
int n;
int tot;
int bl[111];
int cnt;
int dfn[111];
int low[111];
int in[111];
int out[111];
int js;
stack<int> sta;
struct node{int v;int nex;
}e[11111];
int hea[111];
int vis[111];
void add(int st,int ed)
{e[js].v=ed;e[js].nex=hea[st];hea[st]=js;js++;
}
void tarjan(int x)
{low[x]=dfn[x]=++tot;sta.push(x);vis[x]=1;for(int i=hea[x];i!=-1;i=e[i].nex){int v=e[i].v;if(!dfn[v]){tarjan(v);low[x]=min(low[x],low[v]);}else if(vis[v]){low[x]=min(low[x],dfn[v]);}}if(low[x]==dfn[x]){cnt++;while(1){int po=sta.top();vis[po]=0;sta.pop();bl[po]=cnt;if(po==x)break;}}
}
void solve()
{while(!sta.empty()){sta.pop();}for(int i=1;i<=n;i++){if(!dfn[i])tarjan(i);}for(int i=1;i<=n;i++){for(int j=hea[i];j!=-1;j=e[j].nex){int v=e[j].v;if(bl[i]!=bl[v]){out[bl[i]]++;in[bl[v]]++;}}}int an1=0;int an2=0;for(int i=1;i<=cnt;i++){if(in[i]==0)an1++;if(out[i]==0)an2++;}if(cnt==1)cout<<"1"<<endl<<"0"<<endl;else cout<<an1<<endl<<max(an1,an2)<<endl;
}
int main()
{while(cin>>n){memset(vis,0,sizeof(vis));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(hea,-1,sizeof(hea));memset(in,0,sizeof(in));memset(out,0,sizeof(out));cnt=0;tot=0;js=0;for(int i=1;i<=n;i++){int a;while(1){cin>>a;if(a==0)break;add(i,a);}}solve();}
}
这篇关于poj 1236 Network of Schools （tarjan）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
