Description
一些学校连入一个电脑网络。那些学校已订立了协议：每个学校都会给其它的一些学校分发软件（称作“接受学校”）。注意如果 B 在 A 学校的分发列表中，那么 A 不必也在 B 学校的列表中。
你要写一个程序计算，根据协议，为了让网络中所有的学校都用上新软件，必须接受新软件副本的最少学校数目（子任务
A）。更进一步，我们想要确定通过给任意一个学校发送新软件，这个软件就会分发到网络中的所有学校。为了完成这个任务，我们可能必须扩展接收学校列表，使其加入新成员。计算最少需要增加几个扩展，使得不论我们给哪个学校发送新软件，它都会到达其余所有的学校（子任务
B）。一个扩展就是在一个学校的接收学校列表中引入一个新成员。
Input
第一行包括一个整数 N：网络中的学校数目（2 <= N <= 100）。学校用前 N 个正整数标识。
接下来 N 行中每行都表示一个接收学校列表（分发列表）。第 i+1 行包括学校 i 的接收学校的标识符。每个列表用 0 结束。空列表只用一个 0 表示。
Output
输出两行。第一行应该包括一个正整数：子任务 A 的解 。
第二行应该包括子任务 B 的解。
Sample Input
5
2 4 3 0
4 5 0
0
0
1 0
Sample Output
1
2
Hint
Source
USACO
强连通分量， 连通性
A 即为tarjan 缩点后的 DAG 上所有入度为 0 的点的数目。因为若点X入度为 0 ，则他不能从其他点处获得软件，所以必须给他一份软件。
B 即为 添加多少条边后，DAG 可变为一个环。感性的理解一下就是 max（入度为0的点，出度为0的点）
1 #include <map>
2 #include <set>
3 #include <cmath>
4 #include <ctime>
5 #include <queue>
6 #include <stack>
7 #include <cstdio>
8 #include <string>
9 #include <vector>
10 #include <cstdlib>
11 #include <cstring>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 #define ll long long
16 #define file(a) freopen(a".in","r",stdin); freopen(a".out","w",stdout);
17
18 inline int gi()
19 {
20 bool b=0; int r=0; char c=getchar();
21 while(c<'0' || c>'9') { if(c=='-') b=!b; c=getchar(); }
22 while(c>='0' && c<='9') { r=r*10+c-'0'; c=getchar(); }
23 if(b) return -r; return r;
24 }
25
26 const int inf = 1e9+7, N = 107, M = 10007;
27 int n,num,f[N],dfn[N],low[N],bl[N],cnt,siz[N],Deep,cd[N],rd[N];
28 bool b[N];
29 struct data
30 {
31 int nx,fr,to;
32 }da[M];
33 stack <int> s;
34
35 inline void add (int fr,int to)
36 {
37 da[++num].fr=fr, da[num].to=to, da[num].nx=f[fr], f[fr]=num;
38 }
39
40 inline void tarjan (int o)
41 {
42 dfn[o]=low[o]=++Deep;
43 s.push (o); b[o]=1;
44 int i,to;
45 for (i=f[o]; i; i=da[i].nx)
46 {
47 to=da[i].to;
48 if (!dfn[to]) tarjan (to), low[o]=min (low[o],low[to]);
49 else if(b[to]) low[o]=min (low[o],dfn[to]);
50 }
51 if (low[o] == dfn[o])
52 {
53 cnt++;
54 do { to=s.top(), s.pop(), b[to]=0, bl[to]=cnt; } while (to != o);
55 }
56 }
57
58 int main()
59 {
60 // file("schlnet");
61 n=gi();
62 int i,x,y;
63 for (i=1; i<=n; i++)
64 {
65 x=gi();
66 while (x) add (i,x), x=gi();
67 }
68 for (i=1; i<=n; i++) if (!dfn[i]) tarjan (i);
69 if (cnt == 1) { puts ("1
0"); return 0; }
70 for (i=1; i<=num; i++)
71 {
72 x=bl[da[i].fr], y=bl[da[i].to];
73 if (x != y) cd[x]++, rd[y]++;
74 }
75 x=0, y=0;
76 for (i=1; i<=cnt; i++)
77 {
78 if (!rd[i]) x++;
79 if (!cd[i]) y++;
80 }
81 printf("%d
%d
",x,max (x,y));
82 return 0;
83 }