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

Categories:

题目描述
思路分析
1. 解法一：Kruskal + 枚举边（推荐）
相似题目

题目描述

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

思路分析

解法一：Kruskal + 枚举边（推荐）

核心思路：

先用 Kruskal 求出最小生成树权重 base。

对每条边：

若禁用该边后 MST 权重变大或无法连通，则该边为关键边。

若强制选该边仍能得到 base，则为伪关键边。

复杂度分析：

时间复杂度：O(E^2 log E)。

空间复杂度：O(E + V)。

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

class Solution {
    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
        int m = edges.length;
        int[][] e = new int[m][4];
        for (int i = 0; i < m; i++) {
            e[i][0] = edges[i][0];
            e[i][1] = edges[i][1];
            e[i][2] = edges[i][2];
            e[i][3] = i;
        }
        Arrays.sort(e, Comparator.comparingInt(a -> a[2]));

        int base = kruskal(n, e, -1, -1);
        List<Integer> critical = new ArrayList<>();
        List<Integer> pseudo = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            int w1 = kruskal(n, e, i, -1);
            if (w1 > base) {
                critical.add(e[i][3]);
                continue;
            }
            int w2 = kruskal(n, e, -1, i);
            if (w2 == base) {
                pseudo.add(e[i][3]);
            }
        }

        List<List<Integer>> res = new ArrayList<>();
        res.add(critical);
        res.add(pseudo);
        return res;
    }

    private int kruskal(int n, int[][] e, int ban, int force) {
        UnionFind uf = new UnionFind(n);
        int total = 0;
        if (force != -1) {
            int[] edge = e[force];
            if (uf.union(edge[0], edge[1])) {
                total += edge[2];
            }
        }

        for (int i = 0; i < e.length; i++) {
            if (i == ban) {
                continue;
            }
            int[] edge = e[i];
            if (uf.union(edge[0], edge[1])) {
                total += edge[2];
            }
        }

        return uf.count == 1 ? total : Integer.MAX_VALUE;
    }

    static class UnionFind {
        int[] parent;
        int[] size;
        int count;

        UnionFind(int n) {
            parent = new int[n];
            size = new int[n];
            count = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        int find(int x) {
            while (x != parent[x]) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }

        boolean union(int a, int b) {
            int ra = find(a);
            int rb = find(b);
            if (ra == rb) {
                return false;
            }
            if (size[ra] < size[rb]) {
                int t = ra;
                ra = rb;
                rb = t;
            }
            parent[rb] = ra;
            size[ra] += size[rb];
            count--;
            return true;
        }
    }
}

import "sort"

type Edge struct {
    u   int
    v   int
    w   int
    idx int
}

type UnionFind struct {
    parent []int
    size   []int
    count  int
}

func newUnionFind(n int) *UnionFind {
    parent := make([]int, n)
    size := make([]int, n)
    for i := 0; i < n; i++ {
        parent[i] = i
        size[i] = 1
    }
    return &UnionFind{parent: parent, size: size, count: n}
}

func (uf *UnionFind) find(x int) int {
    for x != uf.parent[x] {
        uf.parent[x] = uf.parent[uf.parent[x]]
        x = uf.parent[x]
    }
    return x
}

func (uf *UnionFind) union(a, b int) bool {
    ra := uf.find(a)
    rb := uf.find(b)
    if ra == rb {
        return false
    }
    if uf.size[ra] < uf.size[rb] {
        ra, rb = rb, ra
    }
    uf.parent[rb] = ra
    uf.size[ra] += uf.size[rb]
    uf.count--
    return true
}

func kruskal(n int, edges []Edge, ban int, force int) int {
    uf := newUnionFind(n)
    total := 0
    if force != -1 {
        e := edges[force]
        if uf.union(e.u, e.v) {
            total += e.w
        }
    }

    for i, e := range edges {
        if i == ban {
            continue
        }
        if uf.union(e.u, e.v) {
            total += e.w
        }
    }

    if uf.count != 1 {
        return 1 << 60
    }
    return total
}

func findCriticalAndPseudoCriticalEdges(n int, edgesInput [][]int) [][]int {
    edges := make([]Edge, len(edgesInput))
    for i, e := range edgesInput {
        edges[i] = Edge{u: e[0], v: e[1], w: e[2], idx: i}
    }
    sort.Slice(edges, func(i, j int) bool {
        return edges[i].w < edges[j].w
    })

    base := kruskal(n, edges, -1, -1)
    critical := make([]int, 0)
    pseudo := make([]int, 0)

    for i := 0; i < len(edges); i++ {
        w1 := kruskal(n, edges, i, -1)
        if w1 > base {
            critical = append(critical, edges[i].idx)
            continue
        }
        w2 := kruskal(n, edges, -1, i)
        if w2 == base {
            pseudo = append(pseudo, edges[i].idx)
        }
    }

    return [][]int{critical, pseudo}
}

相似题目

题目	难度	考察点
1135. 最低成本联通所有城市	中等	最小生成树
1584. 连接所有点的最小费用	中等	最小生成树
1319. 连通网络的操作次数	中等	并查集
261. 以图判树	中等	并查集
684. 冗余连接	中等	并查集

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/43776039