接触过数据结构的读者都知道，数据结构里囊括了很多种存储数据的方案，包括线性表、树、图等。线性表的特征非常明显，很容易辨识，树和图是初学者经常混淆的。

在数据结构中，所有的树都可以看做是图型结构，但反过来，只有「连通且不存在环路的无向图」可以看做是树型结构。例如，观察下方哪个是树型结构，哪个是图型结构？

图 1 树和图的区别

图 1 中，c) 是有向图，无法被看做是树型结构。重点观察 a) 和 b)，它们都是无向图，并且各自包含的顶点都是相互连通的，唯一的不同在于，b) 中存在 1-0-2-1 这条环路，而 a) 中不存在环路，因此 a) 既可以看做是一张图，也可以看做是一棵树；而 b) 只能看做是一张图。

本节要带领大家解决的冗余连接问题，指的是给定一张图型结构，它是由 n 个顶点的树外加一条边构成的，要求找出这条冗余的边。图中所有边的信息都记录在长度为 n 的二维数组 edges 里，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。如果有多条符合条件的边，则返回 edges 数组中最后出现的那个。

举个简单的例子，从下图中找到冗余的那条边。

图 2 给定的图

观察图 2 不难发现，冗余的边可以是 [1, 2]、[1, 3]、[2, 3] 中的任意一条，删除它们中的一个，剩下的就是一棵树。当然多条符合条件的边时，题目要求返回 edges 数组中最后出现的那个，也就是 [2, 3] 这条边。

冗余连接问题可以用并查集解决，接下来给大家讲解具体的实现过程。

并查集解决冗余连接问题

并查集解决冗余连接问题的思路是，依次判断 edges 数组中存储的各个边是否是冗余的，判断依据是：如果当前边两端的顶点不属于一个集合，就将它们合并为一个集合；反之，如果当前边两端的顶点属于同一个集合，表明两个顶点先前已经连通过了，再添加当前边会导致出现环路，因此当前边就是冗余的。

仍以图 2 为例，并查集解决冗余连接问题的过程是：

• 初始状态下，顶点 1、2、3 各自属于不同的集合；
• 检查 [1, 2] 边是否冗余：顶点 1 和 2 位于不同的集合里，因此 [1, 2] 不是冗余的，将顶点 1 和 2 合并为同一个集合；
• 检查 [1, 3] 边是否冗余：顶点 1 和 3 位于不同的集合里，因此 [1, 3] 不是冗余的，将顶点 1 和 3 合并为同一个集合；
• 检查 [2, 3] 边是否冗余：顶点 2 和 3 位于同一个集合里，因此 [2, 3] 是冗余的。

下面是用并查集解决冗余问题的 C 语言程序：

1. #include <stdio.h>
2. #include <stdlib.h>
3. 
   
4. typedef enum { false, true } bool;
5. #define MAX_SIZE 1000  // 可以根据需要调整最大尺寸
6. 
   
7. // 并查集数组
8. typedef struct {
9. int parent[MAX_SIZE];
10. int count;
11. }UnionFind;
12. 
    
13. // 初始化并查集
14. void initialize(UnionFind* uf, int size) {
15. for (int i = 0; i <= size; i++) {
16.        uf->parent[i] = i;
17. }
18.    uf->count = size;
19. }
20. 
    
21. // 查找根节点（代表元素）
22. int find(UnionFind* uf, int x) {
23. if (uf->parent[x] != x) {
24.        uf->parent[x] = find(uf, uf->parent[x]); // 路径压缩
25. }
26. return uf->parent[x];
27. }
28. 
    
29. // 合并两个元素所在的集合
30. void unionSets(UnionFind* uf, int x, int y) {
31. //找到两个元素所在集合的代表元素
32. int xRoot = find(uf, x);
33. int yRoot = find(uf, y);
34. //如果代表元素不同，表明它们是两个集合，将它们合并
35. if (xRoot != yRoot) {
36.        uf->parent[xRoot] = yRoot; // uf->parent[yRoot] = xRoot;
37.        uf->count--;
38. }
39. }
40. 
    
41. int* findRedundantConnection(int(*edgs)[2], int n) {
42. UnionFind uf;
43. initialize(&uf, n);
44. // 遍历所有的边
45. for (int  i = 0; i < n; i++)
46. {
47. //判断当前边是否冗余
48. if (find(&uf, edgs[i][0]) == find(&uf, edgs[i][1])) {
49. return edgs[i];
50. }
51. else
52. {
53. unionSets(&uf, edgs[i][0], edgs[i][1]);
54. }
55. }
56. }
57. 
    
58. int main() {
59. int edgs[3][2] = { {1,2},{1,3},{2,3} };
60. 
    
61. //找到冗余的边
62. int * ret = findRedundantConnection(edgs, 3);
63. printf("冗余的边是：[%d, %d]\n", ret[0], ret[1]);
64. return 0;
65. }

下面是用并查集解决冗余问题的 Java 程序：

1. // 并查集类，用于处理集合合并和查找操作（在 UnionFind.java 文件中）
2. public class UnionFind {
3. private int[] parent;  // 记录节点的父节点
4. private int count;     // 记录集合的数量
5. 
   
6. // 构造函数，初始化并查集，每个节点的父节点初始为自己，集合数量为节点个数
7. public UnionFind(int size) {
8.        parent = new int[size + 1];
9. for (int i = 0; i <= size; i++) {
10.            parent[i] = i;
11. }
12.        count = size;
13. }
14. 
    
15. // 查找根节点（代表元素）的方法，同时进行路径压缩
16. public int find(int x) {
17. if (parent[x] != x) {
18.            parent[x] = find(parent[x]);  // 路径压缩
19. }
20. return parent[x];
21. }
22. 
    
23. // 合并两个元素所在的集合
24. public void unionSets(int x, int y) {
25. int xRoot = find(x);
26. int yRoot = find(y);
27. if (xRoot != yRoot) {
28.            parent[xRoot] = yRoot;  // 合并集合
29.            count--;
30. }
31. }
32. 
    
33. // 获取当前集合的数量
34. public int getCount() {
35. return count;
36. }
37. }
38. 
    
39. // FindRedundantConnection 类定义（在 FindRedundantConnection.java 文件中）
40. public class FindRedundantConnection {
41. // 查找冗余连接的方法
42. public int[] findRedundantConnection(int[][] edges) {
43. UnionFind uf = new UnionFind(edges.length);
44. int[] result = new int[2];
45. for (int[] edge : edges) {
46. if (uf.find(edge[0]) == uf.find(edge[1])) {
47.                result[0] = edge[0];
48.                result[1] = edge[1];
49. } else {
50.                uf.unionSets(edge[0], edge[1]);
51. }
52. }
53. return result;
54. }
55. 
    
56. public static void main(String[] args) {
57. int[][] edges = { {1, 2}, {1, 3}, {2, 3} };
58. 
    
59. FindRedundantConnection validPath = new FindRedundantConnection();
60. int[] result = validPath.findRedundantConnection(edges);
61. 
    
62.        System.out.println("冗余的边是：[" + result[0] + ", " + result[1] + "]");
63. }
64. }

下面是用并查集解决冗余问题的 Python 程序：

1. class UnionFind:
2. def __init__(self, size):
3.        self.parent = [i for i in range(size + 1)]
4.        self.count = size
5. 
   
6. # 初始化并查集
7. def initialize(self, size):
8. for i in range(size + 1):
9.            self.parent[i] = i
10.        self.count = size
11. 
    
12. # 查找操作，返回元素所在集合的代表元素
13. def find(self, x):
14. if self.parent[x] != x:
15.            self.parent[x] = self.find(self.parent[x])  # 路径压缩
16. return self.parent[x]
17. 
    
18. # 合并两个集合
19. def union_sets(self, x, y):
20.        x_root = self.find(x)
21.        y_root = self.find(y)
22. if x_root != y_root:
23.            self.parent[x_root] = y_root
24.            self.count -= 1
25. 
    
26. # 查找冗余连接的方法
27. def find_redundant_connection(edges):
28.    uf = UnionFind(len(edges))
29.    result = [0, 0]
30. for edge in edges:
31. if uf.find(edge[0]) == uf.find(edge[1]):
32.            result[0], result[1] = edge[0], edge[1]
33. else:
34.            uf.union_sets(edge[0], edge[1])
35. return result
36. 
    
37. 
    
38. if __name__ == "__main__":
39.    edges = [[1, 2], [1, 3], [2, 3]]
40. 
    
41.    ret = find_redundant_connection(edges)
42. print(f"冗余的边是：[{ret[0]}, {ret[1]}]")

运行程序，输出结果为：

冗余的边是：[2, 3]接触过数据结构的读者都知道，数据结构里囊括了很多种存储数据的方案，包括线性表、树、图等。线性表的特征非常明显，很容易辨识，树和图是初学者经常混淆的。

在数据结构中，所有的树都可以看做是图型结构，但反过来，只有「连通且不存在环路的无向图」可以看做是树型结构。例如，观察下方哪个是树型结构，哪个是图型结构？

图 1 树和图的区别

图 1 中，c) 是有向图，无法被看做是树型结构。重点观察 a) 和 b)，它们都是无向图，并且各自包含的顶点都是相互连通的，唯一的不同在于，b) 中存在 1-0-2-1 这条环路，而 a) 中不存在环路，因此 a) 既可以看做是一张图，也可以看做是一棵树；而 b) 只能看做是一张图。

本节要带领大家解决的冗余连接问题，指的是给定一张图型结构，它是由 n 个顶点的树外加一条边构成的，要求找出这条冗余的边。图中所有边的信息都记录在长度为 n 的二维数组 edges 里，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。如果有多条符合条件的边，则返回 edges 数组中最后出现的那个。

举个简单的例子，从下图中找到冗余的那条边。

图 2 给定的图

观察图 2 不难发现，冗余的边可以是 [1, 2]、[1, 3]、[2, 3] 中的任意一条，删除它们中的一个，剩下的就是一棵树。当然多条符合条件的边时，题目要求返回 edges 数组中最后出现的那个，也就是 [2, 3] 这条边。

冗余连接问题可以用并查集解决，接下来给大家讲解具体的实现过程。

并查集解决冗余连接问题

并查集解决冗余连接问题的思路是，依次判断 edges 数组中存储的各个边是否是冗余的，判断依据是：如果当前边两端的顶点不属于一个集合，就将它们合并为一个集合；反之，如果当前边两端的顶点属于同一个集合，表明两个顶点先前已经连通过了，再添加当前边会导致出现环路，因此当前边就是冗余的。

仍以图 2 为例，并查集解决冗余连接问题的过程是：

• 初始状态下，顶点 1、2、3 各自属于不同的集合；
• 检查 [1, 2] 边是否冗余：顶点 1 和 2 位于不同的集合里，因此 [1, 2] 不是冗余的，将顶点 1 和 2 合并为同一个集合；
• 检查 [1, 3] 边是否冗余：顶点 1 和 3 位于不同的集合里，因此 [1, 3] 不是冗余的，将顶点 1 和 3 合并为同一个集合；
• 检查 [2, 3] 边是否冗余：顶点 2 和 3 位于同一个集合里，因此 [2, 3] 是冗余的。

下面是用并查集解决冗余问题的 C 语言程序：

1. #include <stdio.h>
2. #include <stdlib.h>
3. 
   
4. typedef enum { false, true } bool;
5. #define MAX_SIZE 1000  // 可以根据需要调整最大尺寸
6. 
   
7. // 并查集数组
8. typedef struct {
9. int parent[MAX_SIZE];
10. int count;
11. }UnionFind;
12. 
    
13. // 初始化并查集
14. void initialize(UnionFind* uf, int size) {
15. for (int i = 0; i <= size; i++) {
16.        uf->parent[i] = i;
17. }
18.    uf->count = size;
19. }
20. 
    
21. // 查找根节点（代表元素）
22. int find(UnionFind* uf, int x) {
23. if (uf->parent[x] != x) {
24.        uf->parent[x] = find(uf, uf->parent[x]); // 路径压缩
25. }
26. return uf->parent[x];
27. }
28. 
    
29. // 合并两个元素所在的集合
30. void unionSets(UnionFind* uf, int x, int y) {
31. //找到两个元素所在集合的代表元素
32. int xRoot = find(uf, x);
33. int yRoot = find(uf, y);
34. //如果代表元素不同，表明它们是两个集合，将它们合并
35. if (xRoot != yRoot) {
36.        uf->parent[xRoot] = yRoot; // uf->parent[yRoot] = xRoot;
37.        uf->count--;
38. }
39. }
40. 
    
41. int* findRedundantConnection(int(*edgs)[2], int n) {
42. UnionFind uf;
43. initialize(&uf, n);
44. // 遍历所有的边
45. for (int  i = 0; i < n; i++)
46. {
47. //判断当前边是否冗余
48. if (find(&uf, edgs[i][0]) == find(&uf, edgs[i][1])) {
49. return edgs[i];
50. }
51. else
52. {
53. unionSets(&uf, edgs[i][0], edgs[i][1]);
54. }
55. }
56. }
57. 
    
58. int main() {
59. int edgs[3][2] = { {1,2},{1,3},{2,3} };
60. 
    
61. //找到冗余的边
62. int * ret = findRedundantConnection(edgs, 3);
63. printf("冗余的边是：[%d, %d]\n", ret[0], ret[1]);
64. return 0;
65. }

下面是用并查集解决冗余问题的 Java 程序：

1. // 并查集类，用于处理集合合并和查找操作（在 UnionFind.java 文件中）
2. public class UnionFind {
3. private int[] parent;  // 记录节点的父节点
4. private int count;     // 记录集合的数量
5. 
   
6. // 构造函数，初始化并查集，每个节点的父节点初始为自己，集合数量为节点个数
7. public UnionFind(int size) {
8.        parent = new int[size + 1];
9. for (int i = 0; i <= size; i++) {
10.            parent[i] = i;
11. }
12.        count = size;
13. }
14. 
    
15. // 查找根节点（代表元素）的方法，同时进行路径压缩
16. public int find(int x) {
17. if (parent[x] != x) {
18.            parent[x] = find(parent[x]);  // 路径压缩
19. }
20. return parent[x];
21. }
22. 
    
23. // 合并两个元素所在的集合
24. public void unionSets(int x, int y) {
25. int xRoot = find(x);
26. int yRoot = find(y);
27. if (xRoot != yRoot) {
28.            parent[xRoot] = yRoot;  // 合并集合
29.            count--;
30. }
31. }
32. 
    
33. // 获取当前集合的数量
34. public int getCount() {
35. return count;
36. }
37. }
38. 
    
39. // FindRedundantConnection 类定义（在 FindRedundantConnection.java 文件中）
40. public class FindRedundantConnection {
41. // 查找冗余连接的方法
42. public int[] findRedundantConnection(int[][] edges) {
43. UnionFind uf = new UnionFind(edges.length);
44. int[] result = new int[2];
45. for (int[] edge : edges) {
46. if (uf.find(edge[0]) == uf.find(edge[1])) {
47.                result[0] = edge[0];
48.                result[1] = edge[1];
49. } else {
50.                uf.unionSets(edge[0], edge[1]);
51. }
52. }
53. return result;
54. }
55. 
    
56. public static void main(String[] args) {
57. int[][] edges = { {1, 2}, {1, 3}, {2, 3} };
58. 
    
59. FindRedundantConnection validPath = new FindRedundantConnection();
60. int[] result = validPath.findRedundantConnection(edges);
61. 
    
62.        System.out.println("冗余的边是：[" + result[0] + ", " + result[1] + "]");
63. }
64. }

下面是用并查集解决冗余问题的 Python 程序：

1. class UnionFind:
2. def __init__(self, size):
3.        self.parent = [i for i in range(size + 1)]
4.        self.count = size
5. 
   
6. # 初始化并查集
7. def initialize(self, size):
8. for i in range(size + 1):
9.            self.parent[i] = i
10.        self.count = size
11. 
    
12. # 查找操作，返回元素所在集合的代表元素
13. def find(self, x):
14. if self.parent[x] != x:
15.            self.parent[x] = self.find(self.parent[x])  # 路径压缩
16. return self.parent[x]
17. 
    
18. # 合并两个集合
19. def union_sets(self, x, y):
20.        x_root = self.find(x)
21.        y_root = self.find(y)
22. if x_root != y_root:
23.            self.parent[x_root] = y_root
24.            self.count -= 1
25. 
    
26. # 查找冗余连接的方法
27. def find_redundant_connection(edges):
28.    uf = UnionFind(len(edges))
29.    result = [0, 0]
30. for edge in edges:
31. if uf.find(edge[0]) == uf.find(edge[1]):
32.            result[0], result[1] = edge[0], edge[1]
33. else:
34.            uf.union_sets(edge[0], edge[1])
35. return result
36. 
    
37. 
    
38. if __name__ == "__main__":
39.    edges = [[1, 2], [1, 3], [2, 3]]
40. 
    
41.    ret = find_redundant_connection(edges)
42. print(f"冗余的边是：[{ret[0]}, {ret[1]}]")

运行程序，输出结果为：

冗余的边是：[2, 3]