LeetCode 684.冗余连接 – JavaScript(并查集+DFS)

这是我参与8月更文挑战的第16天，活动详情查看：8月更文挑战

说明:文章部分内容及图片出自网络，如有侵权请与我本人联系(主页有公众号:小攻城狮学前端)

作者：小只前端攻城狮、 主页：小只前端攻城狮的主页、 来源：掘金

GitHub：P-J27、 CSDN：PJ想做前端攻城狮

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

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 个集合。代码实现如下：

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));
    }
  }
}
​
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 是否相连。如果可以，则它是重复边。

var findRedundantConnection = function(edges) {
    const grah = [], visited = new Uint8Array(edges.length + 1), d = (x, y) => {
        if (x === y) return true
        if (visited[x] || !grah[x]) return false
        visited[x] = 1
        for (let i = 0; i < grah[x].length; i++) if (d(grah[x][i], y)) return true
    }
    for (let i = 0; i < edges.length; i++) {
        const x = edges[i][0], y = edges[i][1]
        visited.fill(0)
        if (d(x, y)) return [x, y]
        if (!grah[x]) grah[x] = []
        grah[x].push(y)
        if (!grah[y]) grah[y] = []
        grah[y].push(x)
    }
};

拓展思考：为什么不能使用集合（Set）？

在完成并查集的解法后，我又用了 Set 这种数据结构来尝试这题，如下所示：

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 指向，一直查找，最终查找到的节点可以视为这个连通分量的根节点。连通分量中的其他节点都是指向它的，因此它可以用来标识连通分量。

感谢阅读，希望能对你有所帮助,文章若有错误或者侵权，可以在评论区留言或在我的主页添加公众号联系我。

写作不易，如果觉得不错，可以「点赞」+「评论」 谢谢支持❤