Tarjan 它好贱，wa了10+次。。。
思路：用“它贱”进行强连通缩点。然后统计缩点后的图中入度为0的点的个数in和出度为0的点到个数out。A就是in， B就是max(in, out);
渣代码：
View Code 1 #include2 #include 3 #include 4 #include 5 6 using namespace std; 7 8 const int N = 110; 9 10 struct node { 11 int to; 12 int next; 13 } g[N*N/2]; 14 15 int head[N], blong[N]; 16 int dfn[N], low[N]; 17 int in[N], out[N]; 18 int t, cnt, ind; 19 bool vis[N]; 20 21 stack s; 22 23 void init() { 24 memset(g, 0, sizeof(g)); 25 memset(head, 0, sizeof(head)); 26 memset(blong, 0, sizeof(blong)); 27 memset(dfn, 0, sizeof(dfn)); 28 memset(low, 0, sizeof(low)); 29 memset(in, 0, sizeof(in)); 30 memset(out, 0, sizeof(out)); 31 memset(vis, 0, sizeof(vis)); 32 t = 1; cnt = ind = 0; 33 } 34 35 void add(int u, int v) { 36 g[t].to = v; g[t].next = head[u]; head[u] = t++; 37 } 38 39 void tarjan(int u) { 40 int v, i; 41 vis[u] = true; 42 s.push(u); 43 low[u] = dfn[u] = ++ind; 44 for(i = head[u]; i; i = g[i].next) { 45 v = g[i].to; 46 if(!dfn[v]) { 47 tarjan(v); 48 low[u] = min(low[u], low[v]); 49 } else if(vis[v]) { 50 low[u] = min(low[u], dfn[v]); 51 } 52 } 53 if(low[u] == dfn[u]) { 54 cnt++; 55 do { 56 v = s.top(); 57 s.pop(); 58 //printf("%d %d\n", v, cnt); 59 blong[v] = cnt; 60 vis[v] = false; 61 } while(v != u); 62 } 63 } 64 65 int main() { 66 //freopen("data.in","r", stdin); 67 68 int i, j, v, a, b, n; 69 while(~scanf("%d", &n)) { 70 init(); 71 for(i = 1; i <= n; i++) { 72 while(scanf("%d", &v), v) { 73 add(i, v); 74 } 75 } 76 77 for(i = 1; i <= n; i++) { 78 if(!dfn[i]) tarjan(i); 79 } 80 81 for(i = 1; i <= n; i++) { 82 for(j = head[i]; j; j = g[j].next) { 83 v = g[j].to; 84 if(blong[i] != blong[v]) { 85 in[blong[v]]++; out[blong[i]]++; 86 } 87 } 88 } 89 a = b = 0; 90 for(i = 1; i <= cnt; i++) { 91 if(!in[i]) a++; 92 if(!out[i]) b++; 93 } 94 printf("%d\n", a); 95 if(cnt == 1) printf("0\n"); 96 else printf("%d\n", max(a, b)); 97 } 98 return 0; 99 }