罗罗编程学习记录
本页内容 展开查看

02.12.1 强连通分量与 Tarjan 及割点桥

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.12 图与字符串进阶

覆盖范围

  • Tarjan 求 SCC
  • Kosaraju 算法
  • 割点与桥
  • 缩点 DAG

高频题速览

编号 题目 难度 频率
02.12.1-001 Tarjan 求强连通分量 高级 ★★★★
02.12.1-002 Kosaraju 算法 进阶 ★★★
02.12.1-003 割点判定 进阶 ★★★
02.12.1-004 桥判定 进阶 ★★★
02.12.1-005 缩点 DAG 高级 ★★★
02.12.1-006 Tarjan 伪代码 高级 ★★★★
02.12.1-007 强连通分量应用 进阶 ★★★
02.12.1-008 点双与边双连通分量 高级 ★★

02.12.1-001 Tarjan 求强连通分量

频率 ★★★★ | 难度 高级

一句话结论

Tarjan 用 DFS,维护 dfn[u](访问时间)和 low[u](子树中能回到的最早 dfn);栈存当前路径上的节点;当 low[u] == dfn[u] 时,栈中 u 及以上节点构成一个 SCC。

概念解释

  • dfn[u]:DFS 访问 u 的时间戳。
  • low[u]:u 或 u 的子树中能通过一条回边回到的最早 dfn。
  • 栈:存当前 DFS 路径上的节点。
  • SCC 判定:low[u] == dfn[u] 时,栈中 u 及以上构成 SCC。

原理流程

  1. dfn[u] = low[u] = ++time,u 入栈。
  2. 遍历 u 的邻接 v:
    • 若 v 未访问:dfs(v),low[u] = min(low[u], low[v])。
    • 若 v 在栈中:low[u] = min(low[u], dfn[v])。
  3. 若 low[u] == dfn[u]:弹出栈直到 u,这些节点构成 SCC。

代码 / 示例

class TarjanSCC {
    private int time = 0;
    private final int[] dfn, low;
    private final boolean[] inStack;
    private final java.util.Deque<Integer> stack = new java.util.ArrayDeque<>();
    private final java.util.List<java.util.List<Integer>> sccs = new java.util.ArrayList<>();
    private final java.util.List<Integer>[] graph;

    TarjanSCC(java.util.List<Integer>[] graph) {
        this.graph = graph;
        int n = graph.length;
        dfn = new int[n]; low = new int[n]; inStack = new boolean[n];
    }
    void dfs(int u) {
        dfn[u] = low[u] = ++time;
        stack.push(u); inStack[u] = true;
        for (int v : graph[u]) {
            if (dfn[v] == 0) {
                dfs(v);
                low[u] = Math.min(low[u], low[v]);
            } else if (inStack[v]) {
                low[u] = Math.min(low[u], dfn[v]);
            }
        }
        if (low[u] == dfn[u]) {
            java.util.List<Integer> scc = new java.util.ArrayList<>();
            while (true) {
                int x = stack.pop();
                inStack[x] = false;
                scc.add(x);
                if (x == u) break;
            }
            sccs.add(scc);
        }
    }
}

常见误区

  • 误区:回边用 low[v] 而不是 dfn[v];正解:回边(v 在栈中)用 dfn[v],因为 low[v] 可能包含已经弹出的 SCC。
  • 误区:low[u] == dfn[u] 才弹栈;正解:是的,这是 SCC 根节点。

追问 / 延伸

  • Q:时间复杂度? A:O(V+E)。
  • Q:Tarjan vs Kosaraju? A:Tarjan 一次 DFS,Kosaraju 两次 DFS,Tarjan 更省。

02.12.1-002 Kosaraju 算法

频率 ★★★ | 难度 进阶

一句话结论

Kosaraju 两次 DFS:第一次在原图 DFS 按完成时间压栈;第二次在逆图按栈顺序 DFS,每次 DFS 树就是一个 SCC。

概念解释

  • 第一次 DFS:原图,按完成时间压栈。
  • 逆图:所有边反向。
  • 第二次 DFS:逆图,按栈顶顺序 DFS,每次 DFS 树 = 一个 SCC。

原理流程

  1. 第一次 DFS 原图,记录完成顺序(栈)。
  2. 建逆图。
  3. 按栈顶顺序在逆图 DFS,每次 DFS 树就是一个 SCC。

代码 / 示例

class Kosaraju {
    private final java.util.List<Integer>[] graph, revGraph;
    private final boolean[] visited;
    private final java.util.Deque<Integer> stack = new java.util.ArrayDeque<>();
    private final java.util.List<java.util.List<Integer>> sccs = new java.util.ArrayList<>();

    Kosaraju(java.util.List<Integer>[] graph) {
        this.graph = graph;
        int n = graph.length;
        revGraph = new java.util.List[n];
        for (int i = 0; i < n; i++) {
            revGraph[i] = new java.util.ArrayList<>();
            for (int v : graph[i]) revGraph[v].add(i);
        }
        visited = new boolean[n];
    }
    void dfs1(int u) {
        visited[u] = true;
        for (int v : graph[u]) if (!visited[v]) dfs1(v);
        stack.push(u);
    }
    void dfs2(int u, java.util.List<Integer> scc) {
        visited[u] = true;
        scc.add(u);
        for (int v : revGraph[u]) if (!visited[v]) dfs2(v, scc);
    }
    void compute() {
        for (int i = 0; i < graph.length; i++) if (!visited[i]) dfs1(i);
        java.util.Arrays.fill(visited, false);
        while (!stack.isEmpty()) {
            int u = stack.pop();
            if (!visited[u]) {
                java.util.List<Integer> scc = new java.util.ArrayList<>();
                dfs2(u, scc);
                sccs.add(scc);
            }
        }
    }
}

常见误区

  • 误区:第二次 DFS 在原图;正解:第二次在逆图。
  • 误区:按栈底顺序;正解:按栈顶顺序(完成时间最晚的先)。

追问 / 延伸

  • Q:时间复杂度? A:O(V+E),两次 DFS。
  • Q:Kosaraju 优点? A:思路直观,逆图 + 两次 DFS。

02.12.1-003 割点判定

频率 ★★★ | 难度 进阶

一句话结论

割点是删除后图不连通的节点;Tarjan 判定:根节点有 >= 2 个子树则是割点;非根节点 u 存在子节点 v 满足 low[v] >= dfn[u],则 u 是割点(v 的子树无法绕回 u 的祖先)。

概念解释

  • 割点:删除后图不连通。
  • 根节点:子树数 >= 2 则是割点。
  • 非根节点:存在子节点 v,low[v] >= dfn[u],则 u 是割点。

原理流程

  1. DFS 维护 dfn 和 low。
  2. 根节点:子树数 >= 2 则割点。
  3. 非根节点:存在子节点 v,low[v] >= dfn[u],则 u 是割点。

代码 / 示例

// 割点判定(在 Tarjan DFS 中)
int children = 0;
for (int v : graph[u]) {
    if (dfn[v] == 0) {
        children++;
        dfs(v);
        low[u] = Math.min(low[u], low[v]);
        if (parent != -1 && low[v] >= dfn[u]) isArticulation[u] = true;
    } else {
        low[u] = Math.min(low[u], dfn[v]);
    }
}
if (parent == -1 && children >= 2) isArticulation[u] = true;

常见误区

  • 误区:根节点也用 low[v] >= dfn[u];正解:根节点用子树数 >= 2。
  • 误区:low[v] > dfn[u] 而不是 >=;正解:>= 即可,等于说明 v 的子树只能回到 u。

追问 / 延伸

  • Q:割点和桥的关系? A:割点是节点,桥是边,判定类似但条件不同。
  • Q:时间复杂度? A:O(V+E)。

02.12.1-004 桥判定

频率 ★★★ | 难度 进阶

一句话结论

桥是删除后图不连通的边;Tarjan 判定:边 (u, v) 是桥当且仅当 low[v] > dfn[u](v 的子树无法绕回 u 或 u 的祖先)。

概念解释

  • 桥:删除后图不连通的边。
  • 判定:low[v] > dfn[u]。
  • 区别割点:割点是 >=,桥是 >。

原理流程

  1. DFS 维护 dfn 和 low。
  2. 对树边 (u, v)(v 是 u 的子节点):
  3. 若 low[v] > dfn[u],则 (u, v) 是桥。

代码 / 示例

// 桥判定(在 Tarjan DFS 中)
for (int v : graph[u]) {
    if (dfn[v] == 0) {
        dfs(v);
        low[u] = Math.min(low[u], low[v]);
        if (low[v] > dfn[u]) bridge(u, v);
    } else if (v != parent) {
        low[u] = Math.min(low[u], dfn[v]);
    }
}

常见误区

  • 误区:桥判定用 >=;正解:桥用 >,割点用 >=。
  • 误区:忽略 parent 边;正解:无向图 DFS 中要跳过 parent 边。

追问 / 延伸

  • Q:桥和割点区别? A:桥是边,割点是节点;桥条件 >,割点条件 >=。
  • Q:时间复杂度? A:O(V+E)。

02.12.1-005 缩点 DAG

频率 ★★★ | 难度 高级

一句话结论

把每个 SCC 缩成一个点,SCC 之间的边构成 DAG(无环);缩点后可以做拓扑排序、DP 等;DAG 上的问题比一般图简单。

概念解释

  • 缩点:每个 SCC 变成一个点。
  • DAG:SCC 之间无环。
  • 应用:拓扑排序、DP、最长路。

原理流程

  1. Tarjan 求所有 SCC。
  2. 每个 SCC 编号为一个节点。
  3. SCC 之间的边构成 DAG。
  4. 在 DAG 上做拓扑排序或 DP。

代码 / 图示

原图:有环
缩点:每个 SCC 一个点
结果:DAG(无环)

常见误区

  • 误区:缩点后还有环;正解:SCC 之间无环,因为如果有环则两个 SCC 应合并。
  • 误区:缩点后边重复;正解:需要去重,避免重复边。

追问 / 延伸

  • Q:缩点后做什么? A:拓扑排序、DP、最长路。
  • Q:时间复杂度? A:O(V+E)。

02.12.1-006 Tarjan 伪代码

频率 ★★★★ | 难度 高级

一句话结论

Tarjan DFS:设 dfn[u] = low[u] = ++time,u 入栈;遍历邻接 v:未访问则递归并更新 low[u] = min(low[u], low[v]),已访问且在栈中则 low[u] = min(low[u], dfn[v]);low[u] == dfn[u] 时弹栈成 SCC。

概念解释

  • dfn:访问时间。
  • low:子树能回到的最早 dfn。
  • 栈:当前路径上的节点。
  • 弹栈:low[u] == dfn[u] 时。

原理流程

见代码。

代码 / 示例

tarjan(u):
  dfn[u] = low[u] = ++time
  stack.push(u); inStack[u] = true
  for v in adj[u]:
    if dfn[v] == 0:
      tarjan(v)
      low[u] = min(low[u], low[v])
    else if inStack[v]:
      low[u] = min(low[u], dfn[v])
  if low[u] == dfn[u]:
    repeat:
      x = stack.pop()
      inStack[x] = false
      scc.add(x)
    until x == u

常见误区

  • 误区:回边用 low[v];正解:回边用 dfn[v]。
  • 误区:弹栈条件 low[u] < dfn[u];正解:== 才弹栈。

追问 / 延伸

  • Q:Tarjan 时间复杂度? A:O(V+E)。
  • Q:Tarjan 能求桥和割点吗? A:能,判定条件不同。

02.12.1-007 强连通分量应用

频率 ★★★ | 难度 进阶

一句话结论

SCC 用于:缩点后做 DAG 上的 DP(如最长路)、2-SAT(强连通分量判断可满足性)、社交网络分析(社区发现)。

概念解释

  • 2-SAT:每个变量取正反两个点,条件转化为边,SCC 判断可满足性。
  • 缩点 DP:DAG 上做最长路/最短路。
  • 社区发现:SCC 内节点互相可达。

原理流程

  1. 2-SAT:变量 x 拆成 x=true 和 x=false,条件转化为蕴含边;若 x 和 !x 在同一 SCC 则不可满足。
  2. 缩点 DP:SCC 缩成点,DAG 上拓扑排序 DP。

代码 / 图示

2-SAT:
  x = true 或 x = false
  条件 (a or b) -> 边 !a -> b, !b -> a
  若 x 和 !x 在同一 SCC -> 不可满足

常见误区

  • 误区:2-SAT 用 Tarjan 还是 Kosaraju? A:都可以,Tarjan 更省。
  • 误区:SCC 内节点等价;正解:SCC 内节点互相可达,在 2-SAT 中可同时取。

追问 / 延伸

  • Q:2-SAT 是什么? A:每个变量取 true/false,条件是两个变量的或,求是否可满足。
  • Q:SCC 还能做什么? A:缩点后做拓扑排序、DP、最短路径。

02.12.1-008 点双与边双连通分量

频率 ★★ | 难度 高级

一句话结论

边双连通分量:内部没有桥(删除任意一条边仍连通);点双连通分量:内部没有割点(删除任意一个节点仍连通);两者都用 Tarjan 判定。

概念解释

  • 边双连通:无桥,删除任意边仍连通。
  • 点双连通:无割点,删除任意节点仍连通。
  • 判定:桥的两个端点属于不同边双;割点可能属于多个点双。

原理流程

  1. 边双连通:先求所有桥,桥把图分成边双。
  2. 点双连通:Tarjan 求割点,割点把图分成点双。

代码 / 图示

边双连通:无桥
点双连通:无割点

常见误区

  • 误区:边双和点双相同;正解:边双是无桥,点双是无割点。
  • 误区:割点属于一个点双;正解:割点可能属于多个点双。

追问 / 延伸

  • Q:边双和点双区别? A:边双删边仍连通,点双删节点仍连通。
  • Q:时间复杂度? A:O(V+E)。

待整理清单

  • [ ] 2-SAT 详细
  • [ ] 圆方树
  • [ ] 强连通分量在工程中的应用