本节介绍一种求解有向图强连通分量的算法—Tarjan算法。

        首先是强连通分量的定义：一个有向图的满足强连通性的子图。所谓强连通性是指这个有向图中任意两点都可以相互联通的性质。
        Tarjan算法基于DFS，要理解这个算法需要先认清一个事实：在强连通图中一定存在一条回路能够遍历所有的点。这也是判定强连通图的充要条件。Tarjan算法就是通过找环来判定强连通性的。
        下面是Tarjan算法的实现过程。
        用栈储存搜索树结点路径。
        对于图中每一个结点，它都有两个量：DFN与LOW。

  • DFN ：这个结点被访问的次序编号，也就是时间戳。
  • LOW ：在搜索树中，这个结点的子树中最小的结点编号（也就是最小的DFN值）。LOW保证了求出的是极大强连通子图。

        注意：每访问一个新结点，首先进行初始化：DFN=LOW=cnt++（cnt是时间戳计数器）并入栈。这是因为新的结点尚未向下扩展，这个结点在搜索树中没有子树，LOW即为自身的DFN。
        每访问到一个结点，遍历该点所有的出边。这时对于每一个出点，有以下几种情况：

  • 该点从未被访问：对该点进行新的Tarjan算法（递归进行），以更新该点的DFN与LOW值。由于该点是原结点在搜索树中的子结点，以此更新原结点LOW值。若原结点为u，该结点为v，那么LOW[u]=min(LOW[u],LOW[v])。
  • 该点已在栈中：直接更新原结点LOW值。需要注意的是，更新方法是LOW[u]=min(LOW[u],DFN[v])。这是因为出点已在栈中，但它也是搜索树的子结点，需要用它的DFN值来更新原结点。
  • 其余情况忽略该结点。

        回溯后，如果一个结点的DFN=LOW，说明自己就在以自己为根的搜索树上，即为一个环。此时退栈，直到该点（含该点），得到的序列就是一个强连通分量。

1
2
3
4
5
6
7
8
9
10
11
12
13
void tarjan(int x) {
    DFN[x] = LOW[x] = index++, vis[x] = 1, sta.push(x);
    for (int i = head[x]; i != -1; i = edge[i].next) {
        if (vis[edge[i].to])LOW[x] = min(DFN[edge[i].to], LOW[x]);
        else if (!DFN[edge[i].to])tarjan(edge[i].to), LOW[x] = min(LOW[x], LOW[edge[i].to]);
    }
    if (DFN[x] == LOW[x]) {
        int t;
        do cout << (t = sta.top()) << " ", vis[t] = 0, sta.pop();
        while (t != x);
        cout << endl;
    }
}

        例题一道：洛谷P2341。

题目描述

        每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜>欢”是可以传递的——如果A喜欢B，B喜欢C，那么A也喜欢C。牛栏里共有N 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。

输入输出格式

输入格式：

  • 第一行：两个用空格分开的整数：N和M。

  • 第二行到第M + 1行：每行两个用空格分开的整数：A和B，表示A喜欢B。

输出格式：

一行：单独一个整数，表示明星奶牛的数量。

        本题实质上给定了一个有向图，判断有多少点可以让所有点都能连通到该点。
        由于环的出现，本题不能直接用拓扑排序方法去做。首先应认识到，一个环（即一个强连通分量）与一个点等价，于是可以将图中所有强连通分量都分别缩至一个点，这样就得到有向无环图，拓扑排序便可解决。
        缩点方法是染色法，将同一个强连通分量中的点染成同一种颜色。

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
82
83
84
#include<bits/stdc++.h>

#define N 100005
using namespace std;
struct Edge {
    int to, next;
} edge[50005];
int head[N], cnt = 1, id[N], n, m, vis[N], x, y, DFNt = 1, DFN[N], LOW[N], ID = 1;
int all[N], in[N], rk[N], in2[N];//in是点的入度，in2是强连通分量的入度，rk是强连通分量的拓扑序
stack<int> sta;
queue<int> que;

inline void add(int x, int y) {
    edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}

void tarjan(int x) {
    if (DFN[x])return;//已经求出的直接return
    DFN[x] = LOW[x] = DFNt++, vis[x] = 1, sta.push(x);
    for (int i = head[x]; i; i = edge[i].next) {
        if (vis[edge[i].to])LOW[x] = min(LOW[x], DFN[edge[i].to]);
        else if(!DFN[edge[i].to]) tarjan(edge[i].to), LOW[x] = min(LOW[x], LOW[edge[i].to]);
    }
    if (DFN[x] == LOW[x]) {
        int t;
        do vis[sta.top()] = 0, id[t = sta.top()] = ID, sta.pop(), all[ID]++;//all计数该强连通分量有几个点
        while (t != x);
        ID++;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> x >> y;
        add(x, y);
    }
    for (int i = 1; i <= n; i++)tarjan(i);
    for (int i = 1; i <= n; i++) {
        for (int j = head[i]; j; j = edge[j].next) {
            if (id[i] != id[edge[j].to])in[edge[j].to]++, in2[id[edge[j].to]]++;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!in[i]) {
            que.push(i);//没有入度的点入队
            if (!in2[id[i]])rk[id[i]] = 1;//若强连通分量也没有入度，则标记其拓扑序为1（最低）
        }
    }
    while (!que.empty()) {
        int t = que.front();
        que.pop();
        for (int i = head[t]; i; i = edge[i].next) {
            if (id[edge[i].to] != id[t]) {//同一个强连通分量的点不考虑
                in[edge[i].to]--, in2[id[edge[i].to]]--;//出度减少一
                if (in[edge[i].to] == 0)que.push(edge[i].to);//入度为0的点入队
                if (in2[edge[i].to] == 0)rk[id[edge[i].to]] = rk[id[t]] + 1;//强连通分量入度为0，得出拓扑序
            }
        }
    }
    int maxn = 0, tot = 0, ans;
    for (int i = 1; i < ID; i++) {//找到最大拓扑序
        if (rk[i] > maxn)maxn = rk[i], tot = 1, ans = i;
        else if (rk[i] == maxn)tot++;
        vis[i] = 0;
    }
    if (tot > 1) {//最大拓扑序数量比一个多，一定不成立
        cout << "0";
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        if (rk[id[i]] == maxn)continue;
        for (int j = head[i]; j; j = edge[j].next)if (id[edge[j].to] != id[i])vis[id[i]] = 1;
    }
    for (int i = 1; i < ID; i++) {
        if (rk[i] < maxn && !vis[i]) {//拓扑序低于最大拓扑序但没有出度，一定不成立
            cout << "0";
            return 0;
        }
    }
    cout << all[ans];//最后输出该强连通分量的点数
    return 0;
}