概念

  • 强连通：有向图 GG 中，任意两个节点互相可达。

  • 强连通分量 (Strongly Connect Componet,SCC)：原图的一个极大强连通子图。也就是说，一个强连通分量是

    1. 强连通的：强连通分量内任意两个节点互相可达
    2. 极大的：不存在节点 u′u'，使得强连通分量加入 u′u' 后仍然是一个强连通子图。

  • 缩点：如果我们把每个强连通分量中的所有点看成一个点，就构成了一个 SCC 图。这个图一定不会存在有向环，因此是一个 DAG。

强连通分量示意图

如上图左，节点 1、4 单独构成一个 SCC，节点2、5，节点3、6，节点7、8、9、10、11、12 构成了三个 SCC。缩点后得到新图如上图右所示。可以观察到，确实是一个有向无环图。

Tarjan 算法

Tarjan 算法可以在 O(V+E)O(V+E) 的复杂度下，通过一次 DFS 找出一个图的所有强连通分量。另外，Tarjan 算法还可稍加修改，用于求解割点、桥、双连通分量问题。

在讨论 Tarjan 算法之前，我们先了解搜索树。在对有向图进行 DFS 时，会形成一颗搜索树。每次搜索找到一个还没有访问过的节点的时候经过的边，被称为树枝边。如果在搜索的过程中，某条边的终点是一个已经被搜索过的节点，则这条边不是树枝边。

为了求解强连通分量，Tarjan 算法维护了两个值：dfn\text{dfn} 和 low\text{low}。

  1. dfnu\text{dfn}_u：在 DFS 过程中，第一次访问节点 uu 的次序。
  2. lowu\text{low}_u：在 uu 的子树中，通过一条不在搜索树的边上能达到的节点的 dfn\text{dfn} 最小值。

若在节点 uu 搜索完成后有 dfnu=lowu\text{dfn}_u=\text{low}_u，那么 uu 的子树中所有没有被划分的节点都和 uu 在同一个连通分量中。（因为若节点 vv 在 uu 的子树中，且没有被先划分走，那么这个节点一定可以回到 uu）

按照深度优先搜索算法搜索的次序对图中所有的结点进行搜索，维护每个结点的 dfn\text{dfn} 与 low\text{low} 变量，且让搜索到的结点入栈。每当找到一个强连通元素，就按照该元素包含结点数目让栈中元素出栈。在搜索过程中，对于结点 uu 和与其相邻的结点 vv 考虑 3 种情况：

  1. vv 未被访问：继续对 vv 进行深度搜索。在回溯过程中，用 lowv\text{low}_v 更新 lowu\text{low}_u。因为存在从 uu 到 vv 的直接路径，所以 vv 能够回溯到的已经在栈中的结点，u 也一定能够回溯到。
  2. vv 被访问过，已经在栈中：根据 low\text{low} 值的定义，用 dfnv\text{dfn}_v 更新 lowu\text{low}_u。
  3. vv 被访问过，已不在栈中：说明 vv 已搜索完毕，其所在连通分量已被处理，所以不用对其做操作。

写成伪代码形式：

\begin{algorithm}
\caption{Tarjan's Algorithm for SCC}
\begin{algorithmic}
\STATE $s$ $\leftarrow$ an empty stack
\STATE $\text{dfn\_clock}$ $\leftarrow$ 1

\FUNCTION{dfs}{node $n$}
    \STATE $\text{dfn}_n:=\text{low}_n:=\text{dfn\_clock}$
    \STATE $\text{dfn\_clock}:=\text{dfn\_clock}+1$
    \STATE push $n$ in stack $s$
    \FOR{each node $m$ with an edge from $n$ to $m$}
        \IF{m hasn't been visited}
            \STATE \CALL{dfs}{m}
            \STATE $\text{low}_n$ $:=$ $\min(\text{low}_n,\text{low}_m)$
            
        \ELSEIF{m in stack $s$}
            \STATE $\text{low}_n$ $:=$ $\min(\text{low}_n,\text{dfn}_m)$
        \ENDIF
    \ENDFOR

    \IF{$\text{low}_n$=$\text{dfn}_n$}
        \WHILE{u in stack $s$}
            \STATE pop $v$ from $s$
            \STATE add $v$ to SCC
        \ENDWHILE
    \ENDIF
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

应用

受欢迎的牛

洛谷P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G

题意简述：给定一个有向图，求有几个节点，从其余节点均可到达。

求连通分量后，符合条件的节点一定在同一个连通分量中。我们把图进行强连通分量分解后，至多有一个强连通分量满足题目的条件。只需判断缩点后是否只有一个出度为 0 的节点，若只有一个，则答案即为该节点所代表强连通分量内节点个数，否则答案为 0。

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
using namespace std;

const int N = 1e4+5;

stack<int> s;
bool inst[N];
vector<int> G[N];
int dfn[N],low[N],dc=0;

int scc_cnt = 0;
int scc[N];
int scc_size[N];

vector<int> G2[N]; 

bool vis[N];

void tarjan(int u){
    dfn[u]=low[u]=++dc;
    s.push(u);inst[u]=1;
    for(int v:G[u]){
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(inst[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    
    if(low[u]==dfn[u]){
        scc_cnt++;
        while(s.size()){
            int x= s.top(); 
            scc[x]=scc_cnt;
            scc_size[scc_cnt]++;
            inst[x]=0;s.pop();
            if(x==u)break;
        }
    } 
}



int main(){
    int n,m;scanf("%d%d",&n,&m); 
    
    for(int i=0;i<m;i++){
        int u,v;scanf("%d%d",&u,&v);
        G[u].push_back(v); 
    } 
    
    for(int i=1;i<=n;i++){
        if(!dfn[i])tarjan(i);
    }
    
    
    for(int u=1;u<=n;u++){
        for(int v:G[u]){
            int uu=scc[u],vv=scc[v];
            if(uu==vv)continue;
            G2[uu].push_back(vv); 
        } 
    }
    
    
    int ans = -1;
    for(int u=1;u<=scc_cnt;u++){
        if(G2[u].size()==0){
            if(ans != -1){
                puts("0");return 0;
            }
            ans = scc_size[u];
        }
    }
    
    printf("%d\n",ans);
    return 0;
}

校园网 Network of Schools

洛谷P2746 [USACO5.3]校园网Network of Schools

对于任务 1，只需统计缩点后入度为 0 的点的个数。（因为这些节点一定要有，其他都可以从这些节点走到）
对于任务 2，其实是问一张有向图最少添加多少条边成为强连通图。这个问题是这么处理的。缩点后，答案即为 max⁡{入度为0的点的个数,出度为0的点的个数}\max\{\text{入度为0的点的个数},\text{出度为0的点的个数}\}。特殊的，若原图即为强连通图，答案为 0 而不为 1。

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
using namespace std;

const int N = 105;

int n;
vector<int> G[N];

stack<int> s;
int dfs_clock,dfn[N],low[N];
bool in_stack[N];

int scc_cnt,scc_id[N];

void tarjan(int u){
    s.push(u);in_stack[u]=1;
    dfn[u]=low[u]=++dfs_clock;
    for(int v:G[u]){
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(in_stack[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }

    if(low[u]==dfn[u]){
        ++scc_cnt;
        while(1){
            int x=s.top();s.pop();
            in_stack[x]=0;
            scc_id[x]=scc_cnt;
            if(x==u)break;
        }
    }
}

int in[N],out[N]; // 入度、出度

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x;
        while(1){
            scanf("%d",&x);
            if(!x)break;
            G[i].push_back(x);
        }
    }

    for(int i=1;i<=n;i++){
        if(!dfn[i])tarjan(i);
    }

    for(int u=1;u<=n;u++){
        for(int v:G[u]){
            if(scc_id[u]!=scc_id[v]){
                out[scc_id[u]]++;
                in[scc_id[v]]++;
            }
        }
    }
    
    int in0=0,out0=0;
    for(int i=1;i<=scc_cnt;i++){
        if(in[i]==0)in0++;
        if(out[i]==0)out0++;
    }

    printf("%d\n",in0);

    if(scc_cnt==1)puts("0");
    else printf("%d\n",max(in0,out0));

    return 0;
}