# 桥和割点

# 定义

我们称无向图G={V,E}G=\{V,E\}中的一条边ee,当且仅当删除这条边后,图中的连通分量数量增加。也称为割边

我们称无向图G={V,E}G=\{V,E\}中的一个顶点vv割点,当且仅当删除这个顶点(及所有与其相连的边)后,图中的连通分量数量增加。

# Tarjan算法

利用Tarjan算法,可以经过一次DFS,在O(V+E)O(V+E)的时间内求出图中的所有桥和割点。

前置知识

DFS序。

Tarjan算法的核心思想是,除了记录节点的DFS序dfn[u]dfn[u],同时用数组low[u]low[u]记录从uu出发,在不经过从其父节点到其的那条边的情况下,所能到达的节点中最小的DFS序。

# 在线算法

# 练习题

# LC684 - 冗余连接 (opens new window)

提示

本题官方题解提供的是并查集解法,但也可以通过Tarjan算法,从最后一条边开始依次判断是否桥边。如果不是桥边,则是一个冗余连接,可以将其删除。

参考代码(C++)
class Solution {
    int n, idx = 0;
    vector<int> dfn, low;
    vector<vector<int>> adj;
    void tarjan(int u, int p) {
        dfn[u] = low[u] = ++idx;
        for (int v : adj[u]) {
            if (v == p)
                continue;
            if (!dfn[v]) {
                tarjan(v, u);
                low[u] = min(low[u], low[v]);
            } else
                low[u] = min(low[u], dfn[v]);
        }
    }
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        n = edges.size();
        adj = vector<vector<int>>(n + 1);
        for (auto v : edges) {
            adj[v[0]].emplace_back(v[1]);
            adj[v[1]].emplace_back(v[0]);
        }
        dfn = vector<int>(n + 1);
        low = vector<int>(n + 1);
        tarjan(1, 0);
        for (int i = n - 1; i >= 0; --i) {
            int &u = edges[i][0], &v = edges[i][1];
            if (dfn[u] >= low[v] && dfn[v] >= low[u])
                return edges[i];
        }
        return {};
    }
};
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