今天终于第一次写了强连通分量的题目
虽然以前老早就知道有这么个东西，对这个东西也有概念，但是确实从来没有写过判别的算法
原来如此简单，但是确实也很巧妙。
在算法导论上面看到的K算法，方法就是做两遍DFS，因为强连通分量有一个性质，就是如果把所有的边反向，那么它仍然是一个强连通分量。
但是今天我用的是Tarjan算法，据说效率比K算法高很多，事实上也应该是这样，因为Tarjan算法只做了一次DFS
其实思想也很简单，就是一直DFS（u），向下向下向下，如果突然发现有一个点可以回到u了，那么这个肯定是一个强连通分量。
哈哈，是不是很通俗。
严格的定义过程大家可以看这里http://www.cmykrgb123.cn/blog/scc-tarjan/
我也是参考了这个才做出来的Tarjan算法，Wiki上的那个过于庞大了，虽然封装的非常好
说说本题，其实就是找强连通分量，然后把每个强连通分量当成一个“超点”来考虑
如果这个“超点”的入度为零，那么它就必然是一个源头，统计这样的“超点”的个数，就是第一问的答案。
第二问，如果有一个“超点”入度不是0，但是出度是0，那就说明这个“超点”可以给其他“超点”作贡献。
我们就找这样的点对，把入度是0和出度是0的点连起来。
这样匹配过后，剩下的要么全是入度是0的，要么全是出度是0的，这些就没办法了，随便从一个连通分量连接过来一条边就可以了。
所以第二问的答案就是所有的“超点”中，入度是0和出度是0的点大的那个数。
1 import java.io.*;
2 import java.util.*;
3 /*
4 ID: yanglei4
5 LANG: JAVA
6 TASK:schlnet
7 */
8 public class schlnet {
9 boolean[] inStack;
10 int[] DFN;
11 int[] LOW;
12 int index = 0;
13 int[] Stack;
14 int top = 0;
15 int[][] map;
16 int BelongCount = 0;
17 int[] belong;
18
19 public void Tarjan(int i) {
20 DFN[i] = LOW[i] = ++index;
21 inStack[i] = true;
22 Stack[top++] = i;
23 for (int j = 1; j <= map[i][0]; j++) {
24 if (DFN[map[i][j]] == 0) {
25 Tarjan(map[i][j]);
26 if (LOW[map[i][j]] < LOW[i])
27 LOW[i] = LOW[map[i][j]];
28 }
29 else if (inStack[map[i][j]] && DFN[map[i][j]] < LOW[i])
30 LOW[i] = DFN[map[i][j]];
31 }
32 if (DFN[i] == LOW[i]) {
33 int j = 0;
34 do {
35 j = Stack[--top];
36 inStack[j] = false;
37 belong[j] = BelongCount;
38 } while (j != i);
39 BelongCount++;
40 }
41
42 }
43
44 public void done() throws IOException {
45 BufferedReader f = new BufferedReader(new FileReader("schlnet.in"));
46 PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("schlnet.out")));
47 int N = Integer.parseInt(f.readLine());
48 map = new int[N + 1][N + 1];
49 DFN = new int[N + 1];
50 LOW = new int[N + 1];
51 inStack = new boolean[N + 1];
52 Stack = new int[N + 1];
53 belong = new int[N + 1];
54
55 Arrays.fill(belong,-1);
56 for (int i = 1; i <= N; i++) {
57 StringTokenizer st = new StringTokenizer(f.readLine());
58 int len = st.countTokens();
59 map[i][0] = len - 1;
60 for (int j = 1; j <= len - 1; j++)
61 map[i][j] = Integer.parseInt(st.nextToken());
62 }
63
64 for (int i = 1; i <= N; i++) {
65 if (DFN[i] == 0)
66 Tarjan(i);
67 }
68 boolean[][] dis = new boolean[BelongCount + 1][BelongCount + 1];
69 for (int i = 1;i <= N;i++) {
70 for (int k = 1;k <= map[i][0];k++)
71 dis[belong[i] + 1][belong[map[i][k]] + 1] = true;
72 }
73 int[] oud = new int[BelongCount + 1];
74 int[] ind = new int[BelongCount + 1];
75
76 for (int i = 1;i <= BelongCount;i++) {
77 for (int j = 1; j<= BelongCount;j++) {
78 if (i!=j && dis[i][j]) {
79 oud[i]++;
80 ind[j]++;
81 }
82 }
83 }
84
85 int i0 = 0;
86 int o0 = 0;
87 for (int i = 1;i <= BelongCount;i++) {
88 if (ind[i] == 0)
89 i0++;
90 if (oud[i] == 0)
91 o0++;
92 }
93
94 if (BelongCount == 1) {
95 out.println("1");
96 out.println("0");
97 }
98 else {
99 out.println(i0);
100 out.println(i0>o0?i0:o0);
101 }
102 out.close();
103 }
104
105 public static void main(String[] args) throws IOException {
106 schlnet t = new schlnet();
107 t.done();
108 System.exit(0);
109 }
110 }
111