USACO Network of Schools

本题是关于有向图联通性的问题，对于第一问，很容易想到下面的算法：

先提取出所给图中的所有强联通分量（维基百科），然后把在同一个SCC中的点都视为一个点（因为SCC内部的点都可以互相联通），建立一个新的图（这个步骤也叫做“缩点（contraction）”）。缩点的时候要注意排除自环和重边。
接着，检查新图中的所有点，如果发现入度为0的点，那么一定要给这个学校（或者叫学校组）送一份软件。因此，任务A的答案就是入度为0的点的个数。

对于B任务，就需要动一些脑筋了。我们可以换一种方式描述B任务：
对缩点后的图进行操作，添加最少的边，让图中的所有点可以相互联通。
这不就是要我们添加最少的边，让这个图变成一个强联通图。

所以，如果原来的图已经是强联通图（缩点后只有一个点），则输出0即可。那么对于还不是强联通的图呢？

先让我们看一看一强联通图都有什么性质：
要是某个点可以到达所有其他点，那么这个点的出度一定不为0；
同理，每个点的入度也不能为0。

那么，是不是说对于一个缩点后的图（图中已经没有联通分量了）只要满足上面的条件就可以成为强联通图呢？答案是肯定的，读者可以自行验证（Linux下没有比较好的免费做图工具）。

就此，B任务的算法也很明白了：
用两个变量分别存储新图中出度为0、入度为0的点的个数。然后输出较大的那个即可。

B任务的算法要感谢BYVoid的文章。

代码中的Kosaraju算法是参考维基百科的伪代码写的，那个栈是完全没有必要的。
更简单的算法请看NOCOW。

关于B任务算法的正确性粗略证明：
根据强联通分量的性质，缩点后的图一定不存在强联通分量了，因此，也不存在环。所以，缩点后的图是一个或者多个有向无还图（还可能含有孤点），因此，只要让每个点都有入度和出度就可以实现全部强联通。

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004 #include <assert.h>
005 #define MAXNODE 102
006
007 typedef struct node
008 {
009     int v;
010     struct node *next;
011 }NODE;
012
013 NODE *first[MAXNODE],*reverse[MAXNODE];   //adjcent list
014 int N;
015 int scc[MAXNODE];  //SCC
016 int visit[MAXNODE];   //for DFS use
017 int stack[MAXNODE];
018 int instack[MAXNODE];
019 int top;
020 int cnt;  //scc number
021 int adj[MAXNODE][MAXNODE];   //SCC matrix
022 int indeg[MAXNODE],outdeg[MAXNODE];  //in/outdegree of every component
023
024 void addedge(NODE **arr,int u,int v)  //edge from u to v
025 {
026     NODE *p;
027     p = malloc(sizeof(NODE));
028     p->v = v;
029     p->next = arr[u];
030     arr[u] = p;
031 }
032
033 void init()
034 {
035     scanf("%d\n",&N);
036     int i,v;
037     for(i = 1;i <= N;i ++)
038         while(1)
039         {
040             scanf("%d",&v);
041             if(v == 0)    break;
042             addedge(first,i,v);
043             addedge(reverse,v,i);
044         }
045 }
046
047 void push(int v)
048 {
049     stack[top ++] = v;
050 }
051
052 int pop()
053 {
054     assert(top > 0);
055     return stack[--top];
056 }
057
058 void dfs_1(int v)
059 {
060     NODE *p;
061     visit[v] = 1;
062     for(p = first[v];p != NULL;p = p->next)
063         if(!visit[p->v])    dfs_1(p->v);
064     push(v);  //put into stack when all finished
065     instack[v] = 1;
066 }
067
068 void dfs_2(int v)
069 {
070     NODE *p;
071     visit[v] = 1;
072     instack[v] = 0;
073     scc[v] = cnt;
074     for(p = reverse[v];p != NULL;p = p->next)
075         if(!visit[p->v])
076             dfs_2(p->v);
077 }
078
079 void debug2()
080 {
081     int i;
082     for(i = 1;i <= N;i ++)
083         fprintf(stderr,"%d->%d\n",i,scc[i]);
084 }
085
086 void ptnode(NODE **arr,int v)   //debug use
087 {
088     NODE *p;
089     printf("%d -> ",v);
090     for(p = arr[v];p != NULL;p = p->next)
091         printf("%d ",p->v);
092     printf("\n");
093 }
094
095 void newgraph()    //taking SSC as a node, create a new graph
096 {
097     int i,j;
098     NODE *p;
099     memset(adj,0,sizeof(adj));
100     memset(indeg,0,sizeof(indeg));
101     for(i = 1;i <= N;i ++)
102         for(p = first[i];p != NULL;p = p->next)
103         {
104             if(scc[i] != scc[p->v] && adj[scc[i]][scc[p->v]] == 0)
105             {
106                 adj[scc[i]][scc[p->v]] = 1;
107                 outdeg[scc[i]] ++;
108                 indeg[scc[p->v]] ++;
109             }
110         }
111     /*
112     for(i = 1;i <= cnt;i ++)
113         for(j = 1;j <= cnt;j ++)
114             if(adj[i][j])    fprintf(stderr,"%d->%d\n",i,j);
115     */
116 }
117
118 void task_1()
119 {
120     int i;
121     int ans = 0;
122     for(i = 1;i <= cnt;i ++)
123     {
124         //fprintf(stderr,"INDEG[%d]=%d\n",i,indeg[i]);
125         if(indeg[i] == 0)    ans ++;
126     }
127     printf("%d\n",ans);
128 }
129
130 void dfs_mark(int v)
131 {
132     visit[v] = 1;
133     int i;
134     for(i = 1;i <= cnt;i ++)
135         if(adj[v][i] && !visit[i])    dfs_mark(i);
136 }
137
138 void task_2()
139 {
140     if(cnt == 1)
141         {printf("0\n");return;}
142     int i,ans;
143     int in,out;
144     in = out = 0;
145     for(i = 1;i <= cnt;i ++)
146     {
147         if(indeg[i] == 0)    in ++;
148         if(outdeg[i] == 0)    out ++;
149     }
150     if(in > out)    ans = in;
151     else ans = out;
152     printf("%d\n",ans);
153 }
154
155 int main()
156 {
157     int i;
158     freopen("schlnet.in","r",stdin);
159     freopen("schlnet.out","w",stdout);
160     init();
161     top = cnt = 0;
162     memset(visit,0,sizeof(visit));
163     for(i = 1;i <= N;i ++)
164         if(!visit[i])    dfs_1(i);
165     memset(visit,0,sizeof(visit));
166     while(top > 0)  //while stack is not empty
167     {
168         i = pop();
169         if(instack[i] == 0)    continue;
170         cnt ++;
171         dfs_2(i);
172     }
173     newgraph();
174     task_1();
175     task_2();
176     return 0;
177 }