描述

树可以看成是一个连通且 无环 的 无向 图。

给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。

示例

示例 1:
1626676174-hOEVUL-image.png

  1. 输入: edges = [[1,2], [1,3], [2,3]]
  2. 输出: [2,3]

示例 2:

1626676179-kGxcmu-image.png

  1. 输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
  2. 输出: [1,4]

提示

  • n == edges.length
  • 3 <= n <= 1000
  • edges[i].length == 2
  • 1 <= ai < bi <= edges.length
  • ai != bi
  • edges 中无重复元素
  • 给定的图是连通的

解题思路

方法一：并查集

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

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

可以通过并查集寻找附加的边。初始时，每个节点都属于不同的连通分量。遍历每一条边，判断这条边连接的两个顶点是否属于相同的连通分量。

  • 如果两个顶点属于不同的连通分量，则说明在遍历到当前的边之前，这两个顶点之间不连通，因此当前的边不会导致环出现，合并这两个顶点的连通分量。
  • 如果两个顶点属于相同的连通分量，则说明在遍历到当前的边之前，这两个顶点之间已经连通，因此当前的边导致环出现，为附加的边，将当前的边作为答案返回。

代码

  1. class Solution {
  2.     public int[] findRedundantConnection(int[][] edges) {
  3.         int n = edges.length;
  4.         int[] parent = new int[n + 1];
  5.         for (int i = 1; i <= n; i++) {
  6.             parent[i] = i;
  7.         }
  8.         for (int i = 0; i < n; i++) {
  9.             int[] edge = edges[i];
  10.             int node1 = edge[0], node2 = edge[1];
  11.             if (find(parent, node1) != find(parent, node2)) {
  12.                 union(parent, node1, node2);
  13.             } else {
  14.                 return edge;
  15.             }
  16.         }
  17.         return new int[0];
  18.     }
  20.     public void union(int[] parent, int index1, int index2) {
  21.         parent[find(parent, index1)] = find(parent, index2);
  22.     }
  24.     public int find(int[] parent, int index) {
  25.         if (parent[index] != index) {
  26.             parent[index] = find(parent, parent[index]);
  27.         }
  28.         return parent[index];
  29.     }
  30. }

复杂度分析

时间复杂度：O(nlogn)，其中 n 是图中的节点个数。需要遍历图中的 n 条边，对于每条边，需要对两个节点查找祖先，如果两个节点的祖先不同则需要进行合并，需要进行 2 次查找和最多 1 次合并。一共需要进行 2n 次查找和最多 n 次合并，因此总时间复杂度是 O(2nlogn)=O(nlogn)。这里的并查集使用了路径压缩，但是没有使用按秩合并，最坏情况下的时间复杂度是 O(nlogn)，平均情况下的时间复杂度依然是 O(nα(n))，其中 α 为阿克曼函数的反函数，α(n) 可以认为是一个很小的常数。

空间复杂度：O(n)，其中 n 是图中的节点个数。使用数组 parent 记录每个节点的祖先。