nyoj 校园网络 (Tarjan求强连通分量)

有点类似方老师和农场，但是由于是单向边，所以不能按叶子处理，找到出度或者入度为0的最大数目即可。
。。。一定要注意初始化全面！！！
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<string>
  6 #include<queue>
  7 #include<algorithm>
  8 #include<map>
  9 #include<iomanip>
 10 #include<climits>
 11 #include<cmath>
 12 #include<stdlib.h>
 13 #include<vector>
 14 #include<stack>
 15 #include<set>
 16 #define INF 2000000000
 17 #define MAXN 110
 18 #define maxn 100010
 19 #define Mod 1000007
 20 #define N 1010
 21 using namespace std;
 22 typedef long long LL;
 23 
 24 vector<int> G1[maxn], G2[maxn];
 25 int dfn[maxn], low[maxn], instk[maxn], bel[maxn];
 26 int Time, scc_cnt, ans;
 27 int vis[maxn];
 28 int ind[maxn], outd[maxn];
 29 int n, m, u, v;
 30 int x, y, z;
 31 stack<int> S;
 32 
 33 void init()
 34 {
 35     for (int i = 0; i <= n; ++i) {
 36         G1[i].clear();
 37         G2[i].clear();
 38         vis[i] = 0;
 39         ind[i] = 0;
 40         outd[i] = 0;
 41         dfn[i] = 0;
 42         low[i] = 0;
 43     }
 44     Time = scc_cnt;
 45     while (!S.empty()) S.pop();
 46 }
 47 
 48 void read()
 49 {
 50     scanf("%d", &n);
 51     for (int i = 1; i <= n; ++i) {
 52         while (scanf("%d", &m),m) 
 53                 G1[i].push_back(m);
 54     }
 55 }
 56 
 57 void Tarjan(int u)
 58 {
 59     dfn[u] = low[u] = ++Time;
 60     S.push(u);
 61     instk[u] = 1;
 62     for (int i = 0; i < G1[u].size(); ++i) {
 63         int v = G1[u][i];
 64         if (!dfn[v]) {
 65             Tarjan(v);
 66             low[u] = min(low[u], low[v]);
 67         }
 68         else if (instk[v])
 69             low[u] = min(low[u], dfn[v]);
 70     }
 71     if (low[u] == dfn[u]) {
 72         scc_cnt++;
 73         int v;
 74         do {
 75             v = S.top();
 76             S.pop();
 77             instk[v] = 0;
 78             bel[v] = scc_cnt;
 79         } while (v != u);
 80     }
 81 }
 82 
 83 void rebuild()
 84 {
 85     for (int i = 1; i <= n; ++i)
 86         for (int j = 0; j < G1[i].size(); ++j) {
 87             u = bel[i];
 88             v = bel[G1[i][j]];
 89             if (u != v) {
 90                 G2[u].push_back(v);
 91                 ind[v]++;
 92                 outd[u]++;
 93             }
 94 
 95         }
 96     int In = 0, Out = 0;
 97     for (int i = 1; i <= scc_cnt; ++i) {
 98         if (!ind[i]) In++;
 99         if (!outd[i]) Out++;
100     }
101     if (scc_cnt == 1) cout << 0 << endl;
102     else cout << max(In, Out) << endl;
103 }
104 
105 void find_scc()
106 {
107     for (int i = 1; i <= n; ++i)
108         if (!dfn[i]) Tarjan(i);
109 }
110 
111 
112 int main()
113 {
114     int T;
115     scanf("%d", &T);
116     while (T--) {
117         init();
118         read();
119         find_scc();
120         rebuild();
121     }
122     return 0;
123 }