强连通分量题，涉及求强连通分量和缩点，基本是抄的模板，我也是把这题的代码当模板放这里。
做这题的一个收获，缩点后为构造强连通分量，最少要添加几条有向边：统计入度和出度为0的点的数量，取其大者。
1 #include2 #include 3 #include 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 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 }