（连通图模板题出度和入度）Network of Schools--POJ--1236

链接：

http://poj.org/problem?id=1236

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82833#problem/A

题意：学校有一些单向网络，现在需要传一些文件

求：1，求最少需要向几个学校分发文件才能让每个学校都收到，

　　2，需要添加几条网络才能从任意一个学校分发都可以传遍所有学校。

解题思路（参考大神的）：

1. 求出所有强连通分量

2. 每个强连通分量缩成一点，则形成一个有向无环图DAG。

3. DAG上面有多少个入度为0的顶点，问题1的答案就是多少

在DAG上要加几条边，才能使得DAG变成强连通的，问题2的答案就是多少

加边的方法：

要为每个入度为0的点添加入边，为每个出度为0的点添加出边

假定有 n 个入度为0的点，m个出度为0的点，如何加边？

把所有入度为0的点编号 0,1,2,3,4 ....N -1

每次为一个编号为i的入度0点可达的出度0点，添加一条出边，连到编号为(i+1)%N 的那个出度0点,

这需要加n条边

若 m <= n，则

加了这n条边后，已经没有入度0点，则问题解决，一共加了n条边

若 m > n，则还有m-n个入度0点，则从这些点以外任取一点，和这些点都连上边，即可，这还需加m-n条边。

所以，max(m,n)就是第二个问题的解

此外：当只有一个强连通分支的时候，就是缩点后只有一个点，虽然入度出度为0的都有一个，但是实际上不需要增加清单的项了，所以答案是1，0；

代码：

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cmath>
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<cstring>
  7 #include<vector>
  8 using namespace std;
  9 #define N 105
 10 
 11 struct Edge{int v, next;}e[N*N];
 12 
 13 int n, Time, bnt, cnt, top;
 14 int low[N], dfn[N], Head[N], sta[N], InStack[N], belong[N];
 15 
 16 void Init()
 17 {
 18     Time = bnt = cnt = top = 0;
 19     memset(low, 0, sizeof(low));
 20     memset(dfn, 0, sizeof(dfn));
 21     memset(Head, -1, sizeof(Head));
 22 }
 23 void Add(int u, int v)
 24 {
 25     e[cnt].v = v;
 26     e[cnt].next = Head[u];
 27     Head[u] = cnt++;
 28 }
 29 
 30 void Tarjan(int u)
 31 {
 32     int j;
 33     low[u] = dfn[u] = ++Time;
 34     InStack[u] = 1;
 35     sta[++top]=u;
 36 
 37     for(j=Head[u]; j!=-1; j=e[j].next)
 38     {
 39         int v = e[j].v;
 40 
 41         if(!dfn[v])
 42         {
 43             Tarjan(v);
 44             low[u] = min(low[u], low[v]);
 45         }
 46         else if(InStack[v])
 47             low[u] = min(low[u], dfn[v]);
 48     }
 49 
 50     if(dfn[u] == low[u])
 51     {
 52         ++bnt;
 53         do
 54         {
 55             j = sta[top--];
 56             InStack[j] = false;
 57             belong[j] = bnt;
 58         }while(u!=j);
 59     }
 60 }
 61 
 62 int main()
 63 {
 64     while(scanf("%d", &n)!=EOF)
 65     {
 66         int u, v, i, j;
 67 
 68         Init();
 69 
 70         for(i=1; i<=n; i++)
 71         {
 72             while(scanf("%d", &v), v)
 73                 Add(i, v);
 74         }
 75 
 76         for(i=1; i<=n; i++)
 77             if(!dfn[i])
 78             Tarjan(i);
 79 
 80         int r[N]={0}, c[N]={0}, rn=0, cn=0;
 81 
 82         for(i=1; i<=n; i++)
 83         for(j=Head[i]; j!=-1; j=e[j].next)
 84         {
 85             u = belong[i], v = belong[e[j].v];
 86             if(u!=v)
 87             {
 88                 c[u]++;
 89                 r[v]++;
 90             }
 91         }
 92 
 93         for(i=1; i<=bnt; i++)
 94         {
 95             if(r[i]==0) rn++;
 96             if(c[i]==0) cn++;
 97         }
 98 
 99         if(bnt == 1)
100             printf("1
0
");
101         else
102             printf("%d
%d
", rn, max(rn, cn));
103 
104     }
105     return 0;
106 }

勿忘初心

（连通图 模板题 出度和入度）Network of Schools--POJ--1236

（连通图模板题出度和入度）Network of Schools--POJ--1236