题目

题目来源：力扣（LeetCode）

在本问题中, 树指的是一个连通且无环的无向图。
输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。

返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。

示例 1：

输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
解释: 给定的无向图为:
1
/ \
2 - 3

示例 2：

输入: [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]
解释: 给定的无向图为:
5 - 1 - 2
| |
4 - 3

思路分析

在一棵树中，边的数量比节点的数量少 1 。如果一棵树有 N 个节点，则这棵树有 N - 1 条边。这道题中的图在树的基础上多了一条附加的边，因此边的数量也是 N 。

树是一个连通且无环的无向图，在树中多了一条附加的边之后就会出现环，因此附加的边即为导致环出现的边。

可以通过并查集寻找附加的边。初始时，每个节点都属于不同的连通分量，遍历每一条边，判断这条边连接的两个顶点是否属于相同的连通分量：
如果两个顶点属于不同的连通分量，则说明在遍历到当前的边之前，这两个顶点之间不连通，因此当前的边不会导致环出现，合并这两个顶点的连通分量。
如果两个顶点属于相同的连通分量，则说明在遍历到当前的边之前，这两个顶点之间已经连通，因此当前的边导致环出现，为附加的边，将当前的边作为答案返回。

  1. /**
  2.  * @param {number[][]} edges
  3.  * @return {number[]}
  4.  */
  5. var findRedundantConnection = function(edges) {
  6.   // 边的数量
  7.   const nodeCounts = edges.length;
  8.   // 实例化一个并查集
  9.   const uf = new UnionFind(nodeCounts);
  10.   // 历每一条边，判断这条边连接的两个顶点是否属于相同的连通分量
  11.   for (let i = 0; i < nodeCounts; i++) {
  12.     const edge = edges[i];
  13.     // 边连接的两个顶点
  14.     const node1 = edge[0];
  15.     const node2 = edge[1];
  16.     // 判断这条边连接的两个顶点是否属于相同的连通分量
  17.     if (uf.findSet(node1) !== uf.findSet(node2)) {
  18.       // 如果两个顶点属于不同的连通分量，合并这两个顶点的连通分量。
  19.       uf.unite(node1, node2)
  20.     } else {
  21.       // 如果两个顶点属于相同的连通分量，为附加的边，将当前的边作为答案返回。
  22.       return edge
  23.     }
  24.   }
  25.   return [0]
  26. };
  28. // 并查集
  29. class UnionFind {
  30.   constructor(n) {
  31.     // 元素所指向的父节点，parent[i] 表示第 i 个元素所指向的父节点
  32.     // 初始化时, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
  33.     this.parent = new Array(n).fill(0).map((value, index) => index);
  34.     // 树的层数，rank[i] 表示以 i 为根的集合所表示的树的层数
  35.     this.rank = new Array(n).fill(1);
  36.     // 节点的个数
  37.     this.setCount = n;
  38.   }
  40.   // 查找过程，查找元素 index 所在集合的编号(查找树的根节点)
  41.   findSet(index) {
  42.     // 不断去查询自己的父节点，直至根节点
  43.     // 根节点的标志是父节点就是本身  parent[index] == index
  44.     if (this.parent[index] != index) {
  45.       // 递归获取节点的父节点
  46.       this.parent[index] = this.findSet(this.parent[index]);
  47.     }
  48.     // 返回根节点
  49.     return this.parent[index];
  50.   }
  52.   // 合并两个集合
  53.   unite(index1, index2) {
  54.     let root1 = this.findSet(index1);
  55.     let root2 = this.findSet(index2);
  56.     // 根节点不一样，是两个不同的集合(两棵不同的树)
  57.     if (root1 != root2) {
  58.       // 根据树的层数合并集合
  59.       // 
  60.       if (this.rank[root1] < this.rank[root2]) {
  61.         // 这个判断如果 root2 所在树的层数 大于 root1，就交换两个父节点，这样始终让 root1 为父节点
  62.         [root1, root2] = [root2, root1];
  63.       }
  64.       // 将层数多的集合合并到集合少的集合
  65.       this.parent[root2] = root1;
  66.       this.rank[root1] += this.rank[root2];
  67.       this.setCount--;
  68.     }
  69.   }
  71.   getCount() {
  72.     return this.setCount;
  73.   }
  75.   connected(index1, index2) {
  76.     return this.findSet(index1) === this.findSet(index2);
  77.   }
  78. }