[强联通分量_tarjan] 0725

tarjan算法的思路不难理解，用low来标记同一个强联通分量中的点，初始时low[i]=dfn[i]，当访问到已经在当前栈中的顶点时，相当于找到了一个强联通分量的根节点（一个强联通分量中最早访问到的作为根节点），然后递归地更新栈中所有节点，如果遇到low[k]=dfn[k]，说明k就是这个分量的根，于是对之前的所有点出栈并标记（此处标记用连续的值1，2，3代表第几个强联通分量，其实可以直接用low就行，cols记录强联通分量的个数）。

  1 # include <cstdio>
  2 # include <cstring>
  3 
  4 # define N (100 + 5)
  5 # define M (N * N)
  6 
  7 int n, m;
  8 int top, cols, tmpdfn;
  9 char ins[N];
 10 int first[N], dfn[N], low[N], s[N], in[N], out[N], c[N];
 11 int u[M], v[M], next[M];
 12 
 13 int Min(int x, int y)
 14 {
 15     return x<y ? x:y;
 16 }
 17 
 18 void tarjan(int x)
 19 {
 20     dfn[x] = low[x] = ++tmpdfn;
 21     s[top++] = x;
 22     ins[x] = 1;
 23     for (int e = first[x]; e != -1; e = next[e])
 24     {
 25         int y = v[e];
 26         if (!dfn[y])
 27         {
 28             tarjan(y);
 29             low[x] = Min(low[x], low[y]);
 30         }
 31         else if (ins[y])
 32             low[x] = Min(low[x], dfn[y]);
 33     }
 34     if (dfn[x] == low[x])
 35     {
 36         int t;
 37         ++cols;
 38         do
 39         {
 40             t = s[--top];
 41             ins[t] = 0;
 42             c[t] = cols;
 43         } while (x != t);
 44     }
 45 }
 46 
 47 void cal(void)
 48 {
 49     top = 0, cols = 0, tmpdfn = 0;
 50     memset(dfn+1, 0, sizeof(int)*n);
 51     memset(ins+1, 0, sizeof(char)*n);
 52     for (int i = 1; i <= n; ++i) if (!dfn[i])
 53         tarjan(i);
 54 }
 55 
 56 void solve(void)
 57 {
 58     cal();
 59     if (cols == 1)
 60     {
 61         printf("1\n0\n");
 62         return ;
 63     }
 64     memset(in+1, 0, sizeof(int)*cols);
 65     memset(out+1, 0, sizeof(int)*cols);
 66     for (int i = 1; i <= n; ++i)
 67     for (int e = first[i]; e != -1; e = next[e])
 68     {
 69         int j = v[e];
 70         if (c[i] != c[j])
 71         {
 72             ++in[c[j]];
 73             ++out[c[i]];
 74         }
 75     }
 76     int zin = 0, zout = 0;
 77     for (int i = 1; i <= cols; ++i)
 78     {
 79         if (!in[i]) ++zin;
 80         if (!out[i]) ++zout;
 81     }
 82     printf("%d\n%d\n", zin, zin>zout ? zin:zout);
 83 }
 84 
 85 void read_graph(void)
 86 {
 87     memset(first+1, -1, sizeof(int)*n);
 88     for (int i = 1; i <= m; ++i)
 89     {
 90         scanf("%d%d", &u[i], &v[i]);
 91         next[i] = first[u[i]];
 92         first[u[i]] = i;
 93     }
 94 }
 95 
 96 int main()
 97 {
 98     while (~scanf("%d%d", &n, &m))
 99     {
100         read_graph();
101         solve();
102     }
103     
104     return 0;
105 }

targin的主体比较”死板“，整体相比两遍DFS（kosaraju）代码不短多少，只是思路是一条线，复杂度和后者只是常数的区别，但可以使用邻接表加速，后者不好使用。