分析部分摘自：http://www.cnblogs.com/kuangbin/archive/2011/08/07/2130277.html
强连通分量缩点求入度为0的个数和出度为0的分量个数
题目大意：N(2<N<100)各学校之间有单向的网络，每个学校得到一套软件后，可以通过单向网络向周边的学校传输，问题1：初始至少需要向多少个学校发放软件，使得网络内所有的学校最终都能得到软件。2，至少需要添加几条传输线路(边)，使任意向一个学校发放软件后，经过若干次传送，网络内所有的学校最终都能得到软件。
也就是：
给定一个有向图，求：
1) 至少要选几个顶点，才能做到从这些顶点出发，可以到达全部顶点
2) 至少要加多少条边，才能使得从任何一个顶点出发，都能到达全部顶点
顶点数<= 100
解题思路：
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；
Sample Input
5
2 4 3 0
4 5 0
0
0
1 0
Sample Output
1
2
Source
#include<cstdio>
#include<iostream>
#include<cstring>
const int MAXN=;//点数
const int MAXM=;//边数
struct Edge
{
int to,next;
}edge[MAXM];
int head[MAXN],tot;
int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值是1~scc
int Index,top;
int scc;//强连通分量的个数
bool Instack[MAXN];
int num[MAXN];//各个强连通分量包含点的个数，数组编号1~scc
//num数组不一定需要，结合实际情况
int out[MAXN],tmp,Num,ans,in[MAXN];
void addedge(int u,int v)
{
edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++;
}
void Tarjan(int u)
{
int v;
Low[u]=DFN[u]=++Index;
Stack[top++]=u;
Instack[u]=true;
for(int i=head[u];i != -;i=edge[i].next)
{
v=edge[i].to;
if(!DFN[v])
{
Tarjan(v);
if(Low[u] > Low[v])Low[u]=Low[v];
}
else if(Instack[v] && Low[u] > DFN[v])
Low[u]=DFN[v];
}
if(Low[u]==DFN[u])
{
scc++;
do
{
v=Stack[--top];
Instack[v]=false;
Belong[v]=scc;
num[scc]++;
}
while(v != u);
}
}
void solve(int N)
{
memset(out,,sizeof(out));
memset(in,,sizeof(in));
memset(Belong,,sizeof(Belong));
memset(DFN,,sizeof(DFN));
memset(Instack,false,sizeof(Instack));
memset(num,,sizeof(num));
Index=scc=top=;
for(int i=;i <= N;i++)
if(!DFN[i])
Tarjan(i);
}
void init()
{
tot=;
memset(head,-,sizeof(head));
}
int main()
{
int n,m;
int i,j,v;
//freopen("1.in","r",stdin);
while(scanf("%d",&n)!=EOF)
{
init();
int q,p;
for(i=;i<=n;i++)
{
while(scanf("%d",&m)!=EOF)
{
if(m==) break;
addedge(i,m);
}
}
solve(n);
for(i=;i<=n;i++)
{
for(v=head[i];v!=-;v=edge[v].next)
{
if(Belong[i]!=Belong[edge[v].to])
{
out[Belong[i]]++;
in[Belong[edge[v].to]]++; }
}
}
int o0=,i0=;
//printf("%d\n",scc);
for(i=;i<=scc;i++)
{
//printf("%d %d\n",out[i],in[i]);
if(!out[i]) o0++;
if(!in[i]) i0++;
}
if(scc==) {printf("1\n0\n");continue;}
printf("%d\n",i0);
printf("%d\n",i0>o0?i0:o0);
}
return ;
}