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

# 更多资料

若有错误,欢迎指正。若对您有帮助,请给个「关注+点赞」,您的支持是我更新的动力 👇