题目链接：http://poj.org/problem?id=1236
题目大意：
给你一个网络（有向图），有两个任务：
①求出至少同时需要几份副本可以使得整个网络都获得副本
②至少添加多少信息表（有向边）使得副本传到任一点，都可以使得整个网络都获得副本
解题思路：
即给定一个有向图，求：
①至少要选几个顶点，才能做到从这些顶点出发，可以到达全部顶点
②至少要加多少条边，才能使得从任何一个顶点出发，都能到达全部顶点
缩点后，分别求出出度入度为0的点数为sum1,sum2,
问题①的答案就为sum2;
问题②的答案为max(sum1,sum2)(即使得所有点的出度入度都大于0)。
注意，只有一个点时，不需要添加边，答案为1,0。
代码
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stack> 6 #include<vector> 7 using namespace std; 8 const int N=105; 9 10 int n,cnt,num; ???????????????????????????//cnt为当前dfs序，num为缩点编号11 int low[N],dfn[N],fa[N],indeg[N],outdeg[N];//dfn为dfs序,low为节点能够通过返回的最早的祖先(注意这里跟求割边割点里的low不同)12 vector<int>v[N]; ??????????????????????????//fa为节点所属的强联通分量的编号.indeg和outdeg为缩点的入度、出度13 stack<int>sk;14 15 void init(){16 ????cnt=num=0;17 ????for(int i=1;i<=n;i++){18 ????????v[i].clear();19 ????}20 ????memset(fa,0,sizeof(fa));21 ????memset(low,0,sizeof(low));22 ????memset(dfn,0,sizeof(dfn));23 ????memset(indeg,0,sizeof(indeg));24 ????memset(outdeg,0,sizeof(outdeg));25 }26 27 //求强联通分量28 void tarjan(int u){29 ????low[u]=dfn[u]=++cnt;30 ????sk.push(u);31 ????for(int i=0;i<v[u].size();i++){32 ????????int t=v[u][i];33 ????????if(!dfn[t]){ ???????????????????????????????//未被访问34 ????????????tarjan(t);35 ????????????low[u]=min(low[u],low[t]);36 ????????}37 ????????else if(!fa[t]) low[u]=min(low[u],dfn[t]); //被访问过且在栈中38 ????}39 ????if(low[u]==dfn[u]){40 ????????num++;41 ????????while(!sk.empty()){42 ????????????int t=sk.top();43 ????????????sk.pop();44 ????????????fa[t]=num;45 ????????????if(t==u) break;46 ????????}47 ????}48 }49 50 int main(){51 ????while(~scanf("%d",&n)){52 ????????init();53 ????????for(int i=1;i<=n;i++){54 ????????????int x;55 ????????????while(~scanf("%d",&x)&&x) v[i].push_back(x);56 ????????}57 ????????for(int i=1;i<=n;i++){ ?????????????//遍历所有点58 ????????????if(!dfn[i]) tarjan(i);59 ????????}60 ????????for(int i=1;i<=n;i++){ ?????????????//缩点，并求出相应的出度入度是否为0(注意不是求出入度)61 ????????????for(int j=0;j<v[i].size();j++){62 ????????????????int t=v[i][j];63 ????????????????if(fa[t]!=fa[i]){64 ????????????????????outdeg[fa[i]]=1;65 ????????????????????indeg[fa[t]]=1;66 ????????????????}67 ????????????}68 ????????}69 ????????int sum1=0,sum2=0;70 ????????for(int i=1;i<=num;i++){71 ????????????if(outdeg[i]==0)72 ????????????????sum1++;73 ????????????if(indeg[i]==0)74 ????????????????sum2++;75 ????????}76 ????????if(num==1) ?????????????????????????//只有一个点时要特判77 ????????????puts("1\n0");78 ????????else printf("%d\n%d\n",sum2,max(sum1,sum2));79 ????}80 ????return 0;81 }POJ 1236 Network of Schools（tarjan求强连通分量+思维）
原文地址：https://www.cnblogs.com/fu3638/p/8635571.html