题目链接：http://poj.org/problem?id=1236
题目大意：
给你一个网络（有向图），有两个任务：
①求出至少同时需要几份副本可以使得整个网络都获得副本
②至少添加多少信息表（有向边）使得副本传到任一点，都可以使得整个网络都获得副本
解题思路：
即给定一个有向图，求：
①至少要选几个顶点，才能做到从这些顶点出发，可以到达全部顶点
②至少要加多少条边，才能使得从任何一个顶点出发，都能到达全部顶点
缩点后，分别求出出度入度为0的点数为sum1,sum2,
问题①的答案就为sum2;
问题②的答案为max(sum1,sum2)(即使得所有点的出度入度都大于0)。
注意，只有一个点时，不需要添加边，答案为1,0。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;
const int N=; int n,cnt,num; //cnt为当前dfs序，num为缩点编号
int low[N],dfn[N],fa[N],indeg[N],outdeg[N];//dfn为dfs序,low为节点能够通过返回的最早的祖先(注意这里跟求割边割点里的low不同)
vector<int>v[N]; //fa为节点所属的强联通分量的编号.indeg和outdeg为缩点的入度、出度
stack<int>sk; void init(){
cnt=num=;
for(int i=;i<=n;i++){
v[i].clear();
}
memset(fa,,sizeof(fa));
memset(low,,sizeof(low));
memset(dfn,,sizeof(dfn));
memset(indeg,,sizeof(indeg));
memset(outdeg,,sizeof(outdeg));
} //求强联通分量
void tarjan(int u){
low[u]=dfn[u]=++cnt;
sk.push(u);
for(int i=;i<v[u].size();i++){
int t=v[u][i];
if(!dfn[t]){ //未被访问
tarjan(t);
low[u]=min(low[u],low[t]);
}
else if(!fa[t]) low[u]=min(low[u],dfn[t]); //被访问过且在栈中
}
if(low[u]==dfn[u]){
num++;
while(!sk.empty()){
int t=sk.top();
sk.pop();
fa[t]=num;
if(t==u) break;
}
}
} int main(){
while(~scanf("%d",&n)){
init();
for(int i=;i<=n;i++){
int x;
while(~scanf("%d",&x)&&x) v[i].push_back(x);
}
for(int i=;i<=n;i++){ //遍历所有点
if(!dfn[i]) tarjan(i);
}
for(int i=;i<=n;i++){ //缩点，并求出相应的出度入度是否为0(注意不是求出入度)
for(int j=;j<v[i].size();j++){
int t=v[i][j];
if(fa[t]!=fa[i]){
outdeg[fa[i]]=;
indeg[fa[t]]=;
}
}
}
int sum1=,sum2=;
for(int i=;i<=num;i++){
if(outdeg[i]==)
sum1++;
if(indeg[i]==)
sum2++;
}
if(num==) //只有一个点时要特判
puts("1\n0");
else printf("%d\n%d\n",sum2,max(sum1,sum2));
}
return ;
}