文章目录
- 冗余连接
- 思路一
冗余连接
树可以看成是一个连通且 无环 的 无向 图。
给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。
请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。
图一：
图二：
示例 1：
输入: edges = [[1,2], [1,3], [2,3]]
输出: [2,3]示例 2：
输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]
思路一
function findRedundantConnection(edges) {const parent = Array(edges.length + 1).fill(0).map((_, idx) => idx);function find(x) {if (parent[x] !== x) {parent[x] = find(parent[x]);}return parent[x];}function union(x, y) {const rootX = find(x);const rootY = find(y);if (rootX === rootY) return false;parent[rootX] = rootY;return true;}for (const [u, v] of edges) {if (!union(u, v)) {return [u, v];}}return [];
}
讲解
冗余连接问题（Redundant Connection）涉及到一棵无向树，该树有一个额外的边，导致图中出现了环。问题要求找出这条多余的边。这个问题可以通过多种方法解决，例如并查集（Union-Find）、深度优先搜索（DFS）或广度优先搜索（BFS）。这里我将展示使用并查集的解法。
- 初始化并查集：为图中的每个节点创建一个独立的集合，即每个节点的父节点初始化为自己。
- 遍历边：对于给定的每一对边 (u, v)，尝试将这两个节点合并到同一个集合中。如果在合并过程中发现 u 和 v 已经属于同一个集合（即它们有相同的根节点），那么这条边就是多余的边，因为它会导致环的形成。
- 合并操作：在并查集中，合并两个节点的过程需要找到它们各自的根节点，如果根节点不同，就将其中一个的根节点指向另一个的根节点，完成合并。
- 找到多余边：在遍历过程中，一旦发现合并操作会导致环的形成，就返回这条边。
详细解释：
● find() 函数：查找节点的根节点，使用路径压缩优化，即在查找过程中，将沿途的每个节点的父节点直接指向根节点，减少后续查找的层级。
● union() 函数：尝试合并两个节点到同一个集合中。如果它们已经属于同一个集合（有相同的根节点），则返回 false 并停止合并。否则，将其中一个节点的根节点指向另一个节点的根节点。
● 主逻辑：遍历给定的边集合，对每一对边尝试合并。一旦发现合并会导致环的形成（即 union() 返回 false），就返回这对边作为多余边。
