题目链接：http://poj.org/problem?id=1236
题目大意：给出N台电脑,电脑间单向连通传送文件
问题1.网络中最少放几个文件保证所有电脑都能接受到文件
问题2.最少向网络中加几条线保证任意放1个文件所有电脑都能接受到
解题思路：
1.求出强连通分量
2.缩点 ，进行重新构图
3.如果入度为0,说明没有文件传输到该网络。解决问题1，统计入度为0的个数即可
4.一个强连通图的入度和出度都不为0。入度为0相当于根root,出度为0相当于叶子leave.max(root, leave)即为答案。
就是需要加的线数，保证整个网络强连通。
若连通分量个数为0，那么答案为0
代码如下：
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
#define N 105
#define M 10005
struct Edge
{
int v, next;
}edge[M]; int node[N], stack[N], instack[N], dfn[N], out[N], in[N];
int low[N], belong[N], index, cnt_edge, n, m, cnt_tar, top;
int ee[M][]; void add_Edge(int u, int v)
{
edge[cnt_edge].next=node[u];
edge[cnt_edge].v=v;
node[u]=cnt_edge++;
}
void tarjan(int u)
{
int i, j, v;
dfn[u]=low[u]=++index;
stack[++top]=u;
instack[u]=;
for(i=node[u]; i!=-; i=edge[i].next)
{
v=edge[i].v;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u], low[v]);
}
else if(instack[v])
low[u]=min(low[u], dfn[v]);
}
if(dfn[u]==low[u])
{
cnt_tar++;
do
{
j=stack[top--];
instack[j]=;
belong[j]=cnt_tar;
}while(j!=u);
} }
void solve()
{
int i;
top=, index=, cnt_tar=;
memset(dfn, , sizeof(dfn));
memset(low, , sizeof(low));
for(i=; i<=n; i++)
if(!dfn[i])
tarjan(i);
}
int main()
{
int i, u, v;
while(scanf("%d", &n)!=EOF)
{
cnt_edge=, m=;
memset(node, -, sizeof(node));
memset(in, , sizeof(in));
memset(out, , sizeof(out));
for(i=; i<=n; i++)
{
while(scanf("%d", &v))
{
if(v==) break;
ee[m][]=i, ee[m++][]=v;
add_Edge(i, v);
}
}
solve();
for(i=; i<=m; i++)
{
int xx=belong[ee[i][]], yy=belong[ee[i][]];
if(xx!=yy)
{
in[yy]++;
out[xx]++;
}
}
int innum=, outnum=;
for(i=; i<=cnt_tar; i++)
{
if(in[i]==)
innum++;
if(out[i]==)
outnum++;
}
if(cnt_tar==)
printf("1\n0\n");
else
printf("%d\n%d\n", innum, max(innum, outnum));
}
return ;
}