强连通分量

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

题目	难度
1489. 找到最小生成树里的关键边和伪关键边	困难
1568. 使陆地分离的最少天数	困难	TODO

定义

强连通的定义是：有向图 G 强连通是指，G 中任意两个结点连通。

强连通分量（Strongly Connected Components，SCC）的定义是：极大的强连通子图。

1489. 找到最小生成树里的关键边和伪关键边

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Solution1489 {
    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
        int len = edges.length;

        // newEdges[i] = {fromi, toi, weighti, i}
        int[][] newEdges = new int[len][4];
        for (int i = 0; i < len; i++) {
            System.arraycopy(edges[i], 0, newEdges[i], 0, 3);
            newEdges[i][3] = i;
        }
        // 按 weight 升序排序
        Arrays.sort(newEdges, Comparator.comparing(o -> o[2]));

        // Kruskal 算法
        int value = 0;
        UnionFind unionFind = new UnionFind(n);
        for (int i = 0; i < len; i++) {
            if (!unionFind.connected(newEdges[i][0], newEdges[i][1])) {
                unionFind.union(newEdges[i][0], newEdges[i][1]);
                value += newEdges[i][2];
            }
        }

        List<Integer> criticalEdges = new ArrayList<>();
        List<Integer> pseudoCriticalEdges = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            // 关键边
            UnionFind unionFind1 = new UnionFind(n);
            int v = 0;
            for (int j = 0; j < len; j++) {
                if (i != j && !unionFind1.connected(newEdges[j][0], newEdges[j][1])) {
                    unionFind1.union(newEdges[j][0], newEdges[j][1]);
                    v += newEdges[j][2];
                }
            }
            if (unionFind1.count != 1 || v > value) {
                criticalEdges.add(newEdges[i][3]);
                continue;
            }

            // 伪关键边
            unionFind1 = new UnionFind(n);
            unionFind1.union(newEdges[i][0], newEdges[i][1]);
            v = newEdges[i][2];
            for (int j = 0; j < len; j++) {
                if (i != j && !unionFind1.connected(newEdges[j][0], newEdges[j][1])) {
                    unionFind1.union(newEdges[j][0], newEdges[j][1]);
                    v += newEdges[j][2];
                }
            }
            if (v == value) {
                pseudoCriticalEdges.add(newEdges[i][3]);
            }
        }
        return List.of(criticalEdges, pseudoCriticalEdges);
    }

    private static class UnionFind {
        // 记录每个节点的父节点
        int[] parent;
        // 记录每棵树的重量
        int[] rank;
        // (可选) 连通分量
        int count;

        // 0 ~ n-1
        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = i;
            }
            count = n;
        }

        // 返回节点 x 的根节点
        private int find(int x) {
            int ret = x;
            while (ret != parent[ret]) {
                // 路径压缩
                parent[ret] = parent[parent[ret]];
                ret = parent[ret];
            }
            return ret;
        }

        // 将 p 和 q 连通
        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP != rootQ) {
                if (rank[rootP] > rank[rootQ]) {
                    parent[rootQ] = rootP;
                } else if (rank[rootP] < rank[rootQ]) {
                    parent[rootP] = rootQ;
                } else {
                    parent[rootQ] = rootP;
                    // 重量平衡
                    rank[rootP] += 1;
                }
                count--;
            }
        }

        // p 和 q 是否连通
        public boolean connected(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            return rootP == rootQ;
        }
    }
}

1568. 使陆地分离的最少天数

（全文完）