问题描述
给定一个二维数组表示边的集合，每条边表示从某个低数字的节点到高数字的节点的连线，这些边连接后构成一个无向连通图，其中存在一条边，使得这个无向连通图存在一个环，要求将这条边找出并剔除，使得剩下的图不存在环结构，同时仍然保持是一个无向的连通图。如果存在多条边，则返回最后出现的那条边。题目链接：**点我**
样例输入输出
输入：[[1,2], [1,3], [2,3]]
输出：[2,3]
输入：[[1,2], [2,3], [3,4], [1,4], [1,5]]
输出：[1,4]
问题解法
使用并查集算法，对输入的边的节点分别查找其根节点，如果相同，则说明这是一条多余的边，否则合并当前的边。代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| class Solution
{
public int[] findRedundantConnection(int[][] edges)
{
int[] parents = new int[edges.length + 1];
for (int i = 0; i < parents.length; i++)
{
parents[i] = i;
}
for (int[] edge : edges)
{
int uParent = findParent(parents, edge[0]);
int vParent = findParent(parents, edge[1]);
if (uParent != vParent)
{
parents[uParent] = vParent;
}
else
{
return new int[]{edge[0], edge[1]};
}
}
return new int[] {0, 0};
}
private int findParent(int[] parents, int i)
{
if (i == parents[i])
{
return i;
}
int root = findParent(parents, parents[i]);
parents[i] = root;
return root;
}
}
|