双连通分量

• OI Wiki: https://oi-wiki.org/graph/bcc/

题目	难度
1192. 查找集群内的「关键连接」	困难	Tarjan
LCP 54. 夺回据点	困难	点双连通分量缩点

定义

在一张连通的无向图中，对于两个点 u 和 v，如果无论删去哪条边（只能删去一条）都不能使它们不连通，我们就说 u 和 v 边双连通（EBCC）。

在一张连通的无向图中，对于两个点 u 和 v，如果无论删去哪个点（只能删去一个，且不能删 u 和 v 自己）都不能使它们不连通，我们就说 u 和 v 点双连通（VBCC）。

边双连通具有传递性，即，若 x,y 边双连通， y,z 边双连通，则 x,z 边双连通。

点双连通 不 具有传递性，反例如下图，A,B 点双连通，B,C 点双连通，而 A,C 不 点双连通。

1192. 查找集群内的「关键连接」

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution1192 {
    private Map<Integer, List<Integer>> adj;

    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        // 无向图
        adj = new HashMap<>();
        for (List<Integer> connection : connections) {
            int from = connection.get(0);
            int to = connection.get(1);

            adj.computeIfAbsent(from, key -> new ArrayList<>()).add(to);
            adj.computeIfAbsent(to, key -> new ArrayList<>()).add(from);
        }

        int[] ids = new int[n];
        Arrays.fill(ids, -1);

        List<List<Integer>> resList = new ArrayList<>();
        dfs(0, 0, -1, ids, resList);
        return resList;
    }

    private int dfs(int idx, int nodeId, int pre, int[] ids, List<List<Integer>> resList) {
        // tarjan
        ids[idx] = nodeId;

        for (int next : adj.get(idx)) {
            if (next != pre) {
                if (ids[next] == -1) {
                    ids[idx] = Math.min(ids[idx], dfs(next, nodeId + 1, idx, ids, resList));
                } else {
                    ids[idx] = Math.min(ids[idx], ids[next]);
                }
            }
        }

        if (ids[idx] == nodeId && idx != 0) {
            resList.add(Arrays.asList(pre, idx));
        }
        return ids[idx];
    }
}

LCP 54. 夺回据点

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class SolutionLCP54 {
    private static final int S = 0;
    private Map<Integer, List<Integer>> adj;
    private boolean[] isCut;
    private int[] dfn;
    private int[] low;
    private int clk;
    private Deque<Integer> stk;
    private LinkedList<List<Integer>> dcc;

    public long minimumCost(int[] cost, int[][] roads) {
        int n = cost.length;
        if (n == 1) {
            return cost[0];
        }

        adj = new HashMap<>();
        for (int[] road : roads) {
            adj.computeIfAbsent(road[0], key -> new ArrayList<>()).add(road[1]);
            adj.computeIfAbsent(road[1], key -> new ArrayList<>()).add(road[0]);
        }
        isCut = new boolean[n];
        dfn = new int[n];
        low = new int[n];
        clk = 0;
        stk = new ArrayDeque<>();
        dcc = new LinkedList<>();
        tarjan(S);

        // 整张图是一个双连通分量，选择整张图权值最小的点即可
        if (dcc.size() == 1) {
            return Arrays.stream(cost).min().orElseThrow();
        }

        List<Integer> vec = new ArrayList<>();
        for (List<Integer> c : dcc) {
            int cnt = 0;
            int min = Integer.MAX_VALUE;
            for (int x : c) {
                if (isCut[x]) {
                    cnt++;
                } else {
                    min = Math.min(min, cost[x]);
                }
            }
            // 该双连通分量只和一个割点相连，是缩点形成的树的叶子节点
            if (cnt == 1) {
                vec.add(min);
            }
        }

        Collections.sort(vec);
        long res = 0;
        for (int i = 0; i < vec.size() - 1; i++) {
            res += vec.get(i);
        }
        return res;
    }

    private void tarjan(int sn) {
        dfn[sn] = low[sn] = ++clk;
        stk.push(sn);
        int flag = 0;
        for (int fn : adj.getOrDefault(sn, new ArrayList<>())) {
            if (dfn[fn] == 0) {
                tarjan(fn);
                low[sn] = Math.min(low[sn], low[fn]);
                if (low[fn] >= dfn[sn]) {
                    flag++;
                    if (sn != S || flag > 1) {
                        isCut[sn] = true;
                    }

                    int t;
                    dcc.add(new ArrayList<>());
                    do {
                        t = stk.pop();
                        dcc.getLast().add(t);
                    } while (t != fn);
                    dcc.getLast().add(sn);
                }
            } else {
                low[sn] = Math.min(low[sn], dfn[fn]);
            }
        }
    }
}

（全文完）