LeetCode 684.冗余连接 - JavaScript
LeetCode 684.冗余连接 - JavaScript
题目描述：在本问题中, 树指的是一个连通且无环的无向图。
输入一个图，该图由一个有着 N 个节点 (节点值不重复 1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在 1 到 N 中间，这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点 u 和 v 的无向图的边。
返回一条可以删去的边，使得结果图是一个有着 N 个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。
题目分析
题目很长，通俗来说就是有一棵树，然后输入中给出了这颗树中的所有节点连线，除此之外还多给了一条。这条多出来的边会导致不符合树的定义。例如在下面的例子中，多出来的[1, 4]这条边形成了环：
输入: [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]
解释: 给定的无向图为:
5 - 1 - 2
| |
4 - 3解法 1：并查集（DSU）
对一棵树来说，有着唯一的根节点。所有边[u, v]中的 u 和 v 应该都属于同一个集合，从形状上来看，它们都是连接点根节点。
如果[p, q]是重复边，那么 p 和 q 之前应该被记录到了同一集合中。所以每次在加入新边的时候，检查集合中是否已经包含边两边的节点即可。
可以使用并查集来描述这种关系，并且并查集可以快速找到节点集合以及快速合并 2 个集合。代码实现如下：
// ac地址：https://leetcode-cn.com/problems/redundant-connection/
// 原文地址：https://xxoo521.com/2020-02-28-redundant-connection/
class UnionFind {
constructor() {
this.parent = new Map();
}
// 查找元素所在集合
find(x) {
while (this.parent.has(x)) {
x = this.parent.get(x);
}
return x;
}
// 合并两个集合
union(p, q) {
const rootP = this.find(p);
const rootQ = this.find(q);
if (rootP !== rootQ) {
this.parent.set(this.find(p), this.find(q));
}
}
}
/**
* @param {number[][]} edges
* @return {number[]}
*/
var findRedundantConnection = function(edges) {
const uf = new UnionFind();
for (const edge of edges) {
const p = edge[0];
const q = edge[1];
if (uf.find(p) === uf.find(q)) {
return [p, q];
}
uf.union(p, q);
}
return [-1, -1];
};解法 2: DFS
对于边[u, v]使用 DFS，检查 u、v 是否相连。如果可以，则它是重复边。
拓展思考：为什么不能使用集合（Set）？
在完成并查集的解法后，我又用了 Set 这种数据结构来尝试这题，如下所示：
/**
* @param {number[][]} edges
* @return {number[]}
*/
var findRedundantConnection = function(edges) {
const set = new Set();
for (const edge of edges) {
if (set.has(edge[0]) && set.has(edge[1])) {
return edge;
}
set.add(edge[0]).add(edge[1]);
}
return [-1, -1];
};结果自然是没有 ac。错误用例是：
输入：[[3,4],[1,2],[2,4],[3,5],[2,5]]
错误输出：[2,4]错误原因是：Set 不能保证里面的节点都属于同一个「连通分量」。例如 3、4 是连通的，1、2 是连通的，但是这是两个连通分量。
而并查集通过保存节点的 parent 指向，一直查找，最终查找到的节点可以视为这个连通分量的根节点。连通分量中的其他节点都是指向它的，因此它可以用来标识连通分量。