5 2 4 3 0 4 5 0 0 0 1 0Sample Output
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；
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <string> #include <stack> #include <queue> #include <vector> #define inf 0x3f3f3f3f #define met(a,b) memset(a,b,sizeof a) typedef long long ll; using namespace std; const int N = 305; const int M = 24005; int vis[N],dfn[N],low[N],head[N],stack1[N],num[N],out[N],in[N]; int cost[N]; int n,m,tot,son,maxn,tim,top,cut; int ans; struct EDG{int to,next;}edg[N*N]; struct node{ll x,y,r,c;}a[N]; bool cmp(node f,node g){return f.c<g.c;} void add(int u,int v){ edg[tot].to=v;edg[tot].next=head[u];head[u]=tot++; } void init(){ met(head,-1); tot=tim=top=cut=0; met(vis,0); met(edg,0); met(out,0);met(in,0); met(cost,inf); met(stack1,0);met(num,0);met(dfn,0);met(low,0); } void Tarjan(int u) { int v; low[u] = dfn[u] = ++tim; stack1[top++] = u; vis[u] = 1; for(int e = head[u]; e != -1; e = edg[e].next){ v = edg[e].to; if(!dfn[v]){ Tarjan(v); low[u] = min(low[u], low[v]); }else if(vis[v]){ low[u] = min(low[u], dfn[v]); } } if(low[u] == dfn[u]){ cut++; do{ v = stack1[--top]; num[v] = cut; vis[v] = 0; }while(u != v); } } int main() { while(~scanf("%d",&n)){ init(); int u,v,ret=0; for(int i=1;i<=n;i++){ while(~scanf("%d",&u)&&u){ add(i,u); } } for(int i=1;i<=n;i++){ if(!dfn[i])Tarjan(i); } for(int i=1; i<=n; i++) { for(int j=head[i]; j!=-1; j=edg[j].next) { int v=edg[j].to; if(num[i]!=num[v])out[num[i]]++,in[num[v]]++; } } ans=0; if(cut==1)printf("1\n0\n"); else { for(int i=1;i<=cut;i++){ if(!out[i])ans++; if(!in[i])ret++; } printf("%d\n%d\n",ret,max(ret,ans)); } } return 0; }
POJ 1236 Network Of Schools (强连通分量缩点求出度为0的和入度为0的分量个数）
原文：http://www.cnblogs.com/jianrenfang/p/6486513.html