今天終于第一次寫了強連通分量的題目
雖然以前老早就知道有這么個東西，對這個東西也有概念，但是確實從來沒有寫過判別的算法
原來如此簡單，但是確實也很巧妙。
在算法導(dǎo)論上面看到的K算法，方法就是做兩遍DFS，因為強連通分量有一個性質(zhì)，就是如果把所有的邊反向，那么它仍然是一個強連通分量。
但是今天我用的是Tarjan算法，據(jù)說效率比K算法高很多，事實上也應(yīng)該是這樣，因為Tarjan算法只做了一次DFS
其實思想也很簡單，就是一直DFS（u），向下向下向下，如果突然發(fā)現(xiàn)有一個點可以回到u了，那么這個肯定是一個強連通分量。
哈哈，是不是很通俗。
嚴格的定義過程大家可以看這里http://www.cmykrgb123.cn/blog/scc-tarjan/
我也是參考了這個才做出來的Tarjan算法，Wiki上的那個過于龐大了，雖然封裝的非常好
說說本題，其實就是找強連通分量，然后把每個強連通分量當(dāng)成一個“超點”來考慮
如果這個“超點”的入度為零，那么它就必然是一個源頭，統(tǒng)計這樣的“超點”的個數(shù)，就是第一問的答案。
第二問，如果有一個“超點”入度不是0，但是出度是0，那就說明這個“超點”可以給其他“超點”作貢獻。
我們就找這樣的點對，把入度是0和出度是0的點連起來。
這樣匹配過后，剩下的要么全是入度是0的，要么全是出度是0的，這些就沒辦法了，隨便從一個連通分量連接過來一條邊就可以了。
所以第二問的答案就是所有的“超點”中，入度是0和出度是0的點大的那個數(shù)。
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