LeetCode LCR 118. 冗余连接

Categories:

题目描述
思路分析
1. 解法一：并查集检测成环（推荐）
相似题目

题目描述

✅ LCR 118. 冗余连接

思路分析

解法一：并查集检测成环（推荐）

核心思路：

并查集维护连通分量。

遍历每条边 (u, v)，若 u 和 v 已在同一集合，则该边是多余边。

否则合并两集合继续扫描。

复杂度分析：

时间复杂度：O(n α(n))，其中 n 表示节点数。

空间复杂度：O(n)，并查集数组。

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        UnionFind uf = new UnionFind(n + 1);

        for (int[] e : edges) {
            if (!uf.union(e[0], e[1])) {
                return e;
            }
        }
        return new int[0];
    }

    private static class UnionFind {
        private final int[] parent;

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

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

        boolean union(int a, int b) {
            int ra = find(a);
            int rb = find(b);
            if (ra == rb) {
                return false;
            }
            parent[ra] = rb;
            return true;
        }
    }
}

func findRedundantConnection(edges [][]int) []int {
    n := len(edges)
    uf := newUnionFind(n + 1)

    for _, e := range edges {
        if !uf.union(e[0], e[1]) {
            return e
        }
    }
    return []int{}
}

type UnionFind struct {
    parent []int
}

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

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

func (u *UnionFind) union(a, b int) bool {
    ra := u.find(a)
    rb := u.find(b)
    if ra == rb {
        return false
    }
    u.parent[ra] = rb
    return true
}

相似题目

题目	难度	考察点
547. 省份数量	中等	并查集
261. 以图判树	中等	并查集
685. 冗余连接 II	困难	并查集
1319. 连通网络的操作次数	中等	并查集
1579. 保证图可完全遍历	困难	并查集

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/52054082