Leetcode ： 684. 冗余连接

> Problem: 684. 冗余连接

题解：冗余连接 (Redundant Connection)

题目描述

给定一棵包含 n 个节点的树（节点值为 1 到 n），向树中添加一条边后形成一个图。你的任务是找出一条可以删除的边，使得删除后剩余部分仍然是一棵有 n 个节点的树。如果有多个答案，返回在输入数组 edges 中最后出现的那个边。

示例

示例 1

输入: edges = [[1,2],[1,3],[2,3]]
输出: [2,3]

示例 2

输入: edges = [[1,2],[1,3],[1,4],[2,4]]
输出: [2,4]

解题思路

本题可以通过并查集（Union-Find）算法有效地解决。并查集能够快速地管理和查询节点的连通性，适合用于检测图中的环。

步骤

1. 初始化并查集:

   • 创建一个数组 p，用于记录每个节点的父节点，初始时每个节点的父节点是自己。
   • 使用 std::iota 来初始化数组，使得 p[i] = i。

2. 查找函数:

   • 定义一个查找函数 find，通过递归方式找到节点的根节点，并进行路径压缩，以提高后续操作的效率。

3. 遍历边:

   • 遍历所有边，使用查找函数检查两个节点的根节点。
   • 如果两个节点的根节点相同，说明这条边形成了环，返回这条边。
   • 如果不同，将两个节点合并到同一个集合中。

4. 返回结果:

   • 最后返回的边即为可以删除的冗余连接。

代码实现

以下是使用 C++ 实现的完整代码：

#include <vector>
#include <numeric>
#include <functional>

class Solution {
public:
    std::vector<int> findRedundantConnection(std::vector<std::vector<int>>& edges) {
        int n = edges.size(); // 获取边的数量
        std::vector<int> p(n); // 初始化父节点数组
        std::iota(p.begin(), p.end(), 0); // 填充父节点数组，p[i] = i

        // 查找函数，使用递归和路径压缩
        std::function<int(int)> find = [&](int x) {
            return x == p[x] ? x : p[x] = find(p[x]); // 路径压缩
        };

        // 遍历边
        for (int i = 0;; ++i) {
            int pa = find(edges[i][0] - 1); // 查找第一个节点的根节点
            int pb = find(edges[i][1] - 1); // 查找第二个节点的根节点
            if (pa == pb) {
                return edges[i]; // 如果两个节点的根节点相同，说明形成了环，返回这条边
            }
            p[pa] = pb; // 合并两个节点的集合
        }
    }
};

代码解析

1. 初始化父节点数组:

   • 使用 std::iota 填充父节点数组，确保每个节点的父节点最初是自己。

2. 查找函数:

   • 采用路径压缩的方式查找节点的根，减少查找时间。

3. 遍历边并合并:

   • 遍历每条边，检查节点是否在同一个集合中。
   • 如果在同一集合，则返回该边，因为它导致了环的形成。

时间复杂度

• 时间复杂度为 O(n)，其中 n 是边的数量。每条边只处理一次，查找和合并操作的效率通过路径压缩得以提升。

空间复杂度

• 空间复杂度为 O(n)，用于存储父节点数组。

总结

通过并查集的方式，我们能够高效地检测图中冗余连接的边。这个解法不仅清晰而且具有良好的性能，适合处理较大的图结构问题。