强连通分量题，涉及求强连通分量和缩点，基本是抄的模板，我也是把这题的代码当模板放这里。
做这题的一个收获，缩点后为构造强连通分量，最少要添加几条有向边：统计入度和出度为0的点的数量，取其大者。
1 #include <stdio.h> 2 #include <string.h> 3 #include <vector> 4 using namespace std; 5 const int N = 105; 6 int stk[N],col[N],dep[N],low[N]; 7 int cnt,cols,top,ans1,ans2; 8 bool inq[N]; 9 vector <int> a[N]; 10 void DFS(int u) 11 { 12 int i,t,l,v; 13 l = a[u].size(); 14 dep[u] = low[u] = ++cnt; 15 stk[top++] = u; 16 inq[u] = 1; 17 for(i = 0; i < l; i++) 18 { 19 v = a[u][i]; 20 if(!dep[v]) 21 { 22 DFS(v); 23 if(low[v] < low[u]) 24 low[u] = low[v]; 25 } 26 else if(inq[v]) 27 { 28 if(dep[v] < low[u]) 29 low[u] = dep[v]; 30 } 31 } 32 if(dep[u] == low[u]) 33 { 34 cols++; 35 do{ 36 t = stk[--top]; 37 inq[t] = 0; 38 col[t] = cols; 39 }while(t != u); 40 } 41 } 42 void Tarjan(int n) 43 { 44 int in0=0,out0=0,i,j,l,v; 45 int in[N],out[N]; 46 cnt = top = cols = 0; 47 memset(inq,0,sizeof inq); 48 memset(dep,0,sizeof dep); 49 memset(low,0,sizeof low); 50 for(i = 1; i <= n; i++) 51 if(!dep[i]) DFS(i); 52 if(cols == 1) 53 { 54 ans1 = 1; 55 ans2 = 0; 56 return ; 57 } 58 memset(in,0,sizeof in); 59 memset(out,0,sizeof out); 60 for(i = 1; i <= n; i++) 61 { 62 l = a[i].size(); 63 for(j = 0; j < l; j++) 64 { 65 v = a[i][j]; 66 if(col[i] != col[v]) 67 out[col[i]]++, in[col[v]]++; 68 } 69 } 70 for(i = 1; i <= cols; i++) 71 { 72 if(!in[i]) in0++; 73 if(!out[i]) out0++; 74 } 75 ans1 = in0; 76 ans2 = in0 > out0 ?in0 :out0 ; 77 } 78 int main() 79 { 80 int n,i,t; 81 while(~scanf("%d",&n)) 82 { 83 for(i = 1; i <= n; i++) 84 while(scanf("%d",&t),t) 85 a[i].push_back(t); 86 Tarjan(n); 87 printf("%d\n%d\n",ans1,ans2); 88 } 89 return 0; 90 }