LeetCode 684. 冗余连接

Categories:

题目描述
思路分析
1. 解法一：并查集（推荐）
2. 解法二：深度优先搜索
相似题目

题目描述

✅ 684. 冗余连接

思路分析

解法一：并查集（推荐）

核心思路：

题目给出一棵树加上一条多余边形成的图，要求找出并删除那条多余边

使用并查集维护节点的连通性，遍历每条边时判断两端节点是否已经连通

若两端节点已连通，说明加入这条边会形成环，即该边为冗余连接

若两端节点未连通，则执行 union 操作将其合并

复杂度分析：

时间复杂度：O(n·α(n))，其中 n 表示节点数，α 为反阿克曼函数，近似常数

空间复杂度：O(n)，其中 n 为节点数，用于存储并查集的 parent 和 rank 数组

class Solution {
    private int[] parent;
    private int[] rank;

    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        parent = new int[n + 1];
        rank = new int[n + 1];

        // 初始化：每个节点的父节点为自身
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }

        for (int[] edge : edges) {
            int x = edge[0];
            int y = edge[1];

            // 若两端已连通，则当前边为冗余连接
            if (find(x) == find(y)) {
                return edge;
            }

            union(x, y);
        }

        return new int[0];
    }

    private int find(int x) {
        if (parent[x] != x) {
            // 路径压缩
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    private void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) {
            return;
        }

        // 按秩合并
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

func findRedundantConnection(edges [][]int) []int {
    n := len(edges)
    parent := make([]int, n+1)
    rank := make([]int, n+1)

    // 初始化：每个节点的父节点为自身
    for i := 1; i <= n; i++ {
        parent[i] = i
    }

    var find func(x int) int
    find = func(x int) int {
        if parent[x] != x {
            // 路径压缩
            parent[x] = find(parent[x])
        }
        return parent[x]
    }

    union := func(x, y int) bool {
        rootX, rootY := find(x), find(y)
        if rootX == rootY {
            return false
        }

        // 按秩合并
        if rank[rootX] < rank[rootY] {
            parent[rootX] = rootY
        } else if rank[rootX] > rank[rootY] {
            parent[rootY] = rootX
        } else {
            parent[rootY] = rootX
            rank[rootX]++
        }
        return true
    }

    for _, edge := range edges {
        x, y := edge[0], edge[1]

        // 若两端已连通，当前边为冗余连接
        if !union(x, y) {
            return edge
        }
    }

    return nil
}

解法二：深度优先搜索

核心思路：

维护当前已构建的图，遍历每条边前，先通过 DFS 判断两端节点是否已连通

若已连通说明新边会成环，直接返回；否则将该边加入图中继续处理

该方法逻辑直观，但时间复杂度较高

复杂度分析：

时间复杂度：O(n²)，其中 n 表示边数，每条边最坏需要 DFS 遍历所有节点

空间复杂度：O(n)，其中 n 为节点数，用于邻接表和递归栈

class Solution {
    private Map<Integer, List<Integer>> graph = new HashMap<>();

    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;

        // 初始化邻接表
        for (int i = 1; i <= n; i++) {
            graph.put(i, new ArrayList<>());
        }

        for (int[] edge : edges) {
            int x = edge[0];
            int y = edge[1];

            // DFS 检测两点是否已连通
            Set<Integer> visited = new HashSet<>();
            if (hasPath(x, y, visited)) {
                return edge;
            }

            // 双向加边
            graph.get(x).add(y);
            graph.get(y).add(x);
        }

        return new int[0];
    }

    private boolean hasPath(int src, int dst, Set<Integer> visited) {
        if (src == dst) {
            return true;
        }

        visited.add(src);

        for (int next : graph.get(src)) {
            if (!visited.contains(next) && hasPath(next, dst, visited)) {
                return true;
            }
        }

        return false;
    }
}

func findRedundantConnection(edges [][]int) []int {
    n := len(edges)
    graph := make([][]int, n+1)
    for i := range graph {
        graph[i] = []int{}
    }

    var hasPath func(src, dst int, visited map[int]bool) bool
    hasPath = func(src, dst int, visited map[int]bool) bool {
        if src == dst {
            return true
        }

        visited[src] = true

        for _, next := range graph[src] {
            if !visited[next] && hasPath(next, dst, visited) {
                return true
            }
        }

        return false
    }

    for _, edge := range edges {
        x, y := edge[0], edge[1]

        // DFS 检测两点是否已连通
        visited := map[int]bool{}
        if hasPath(x, y, visited) {
            return edge
        }

        // 双向加边
        graph[x] = append(graph[x], y)
        graph[y] = append(graph[y], x)
    }

    return nil
}

相似题目

题目	难度	考察点
685. 冗余连接 II	困难	并查集、有向图
547. 省份数量	中等	并查集、DFS
200. 岛屿数量	中等	并查集、DFS
399. 除法求值	中等	并查集、图
1319. 连通网络的操作次数	中等	并查集
261. 以图判树	中等	并查集、DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/57837413