本文主要是介绍POJ1236 Network of Schools(强连通分量：Tarjan算法)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
学校之间有网络系统，通过网络可以从一个学校定向的传递文件给另一个学校。现在问最少给几个学校传递文件使所有学校都能收到？最少添加几天网络边可以使整个网络连通？
要点：
就是一个基本的强连通分量，将连通分量缩成一个点，入度和出度如果都不为0说明这个点与其他点连通，所以第一问我们只要算出几个点入度为0即可，第二问我们只要算出几个点入度为0，几个点出度为0，取其中最大值即可。理解一下就是，我们只要将所有点的入度和出度改为非0，所以只要把入度为0的点和出度为0的点连接即可，所以取最大值。
| 16068574 | Seasonal | 1236 | Accepted | 172K | 16MS | C++ | 1709B | 2016-09-09 09:02:43 |
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<stack>
using namespace std;
const int maxn=200;
vector<int> g[maxn];
stack<int> s;
int dfn[maxn],low[maxn],belong[maxn];
bool instack[maxn];
int in0[maxn],out0[maxn];
int dfs_clock,cnt,n;void dfs(int u)
{dfn[u]=low[u]=++dfs_clock;s.push(u);instack[u]=true;for(int i=0;i<g[u].size();i++){int v=g[u][i];if(!dfn[v])//如果v还没搜索过要先搜索这个点，因为它的low会改变 {dfs(v);low[u]=min(low[u],low[v]);//回溯时改变u的low }else if(instack[v])//如果v已经搜索过且已经在栈中，说明v到u有一条反向边 {low[u]=min(low[u],dfn[v]);//v为u的祖先，low存储v的dfn值 }}if(low[u]==dfn[u])//相等则说明最远祖先是自己，说明自己是第一个节点 {cnt++;for(;;){int x=s.top();s.pop();belong[x]=cnt;instack[x]=false;if(x==u)break;}}
}
void Tarjan()
{dfs_clock=cnt=0;memset(instack,false,sizeof(instack));memset(dfn,0,sizeof(dfn));for(int i=1;i<=n;i++)if(!dfn[i])dfs(i);
}int main()
{int temp;while(scanf("%d",&n)!=EOF){for(int i=1;i<=n;i++)g[i].clear();for(int i=1;i<=n;i++){while(scanf("%d",&temp)&&temp!=0){g[i].push_back(temp);}}Tarjan();for(int i=1;i<=cnt;i++)in0[i]=out0[i]=0;for(int u=1;u<=n;u++)for(int i=0;i<g[u].size();i++){ int v=g[u][i];if(belong[u]!=belong[v]){in0[belong[v]]++;out0[belong[u]]++;}}int a=0,b=0;for(int i=1;i<=cnt;i++){if(in0[i]==0) a++;if(out0[i]==0) b++;}if(cnt==1)//如果本身就是连通图 printf("1\n0\n");elseprintf("%d\n%d\n",a,max(a,b));}return 0;
}
这篇关于POJ1236 Network of Schools(强连通分量：Tarjan算法)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
