Kosaraju求强连通分量

(Updated: )
(2 mins to read)

反图的强连通分量和原图相同按照反图的逆后序方向遍历原图即可逆后序方向：先遍历与该点相连的节点，最后将该点入栈，栈的反序为逆后序利用bitset可以优化到$O(n^2/32)$，适合稠密图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
namespace Kosaraju
{
  int ord[N], tp, num[N], scc;
  bitset<N> tag, G[N], rG[N], t;
  void init(int n)
  {
    for(int i=1; i<=n; i++) G[i].reset(), rG[i].reset();
  }
  void dfs(int u)
  {
    tag[u] = 0;
    while((t=rG[u]&tag).any())
      dfs(t._Find_first());
    ord[++tp] = u;
  }
  void dfs2(int u)
  {
    num[u] = scc;
    tag[u] = 0;
    while((t=G[u]&tag).any())
      dfs2(t._Find_first());
  }
  void gao(int n)
  {
    tp = scc = 0;
    tag.set();
    for(int i=1; i<=n; i++) if(tag[i]) dfs(i);
    tag.set();
    for(int i=n; i>=1; i--)
      if(tag[ord[i]])
      {
        ++scc;
        dfs2(ord[i]);
      }
  }
}