# LWC 51：684. Redundant Connection

## LWC 51：684. Redundant Connection

Problem:

We are given a “tree” in the form of a 2D-array, with distinct values for each node. In the given 2D-array, each element pair [u, v] represents that v is a child of u in the tree. We can remove exactly one redundant pair in this “tree” to make the result a tree. You need to find and output such a pair. If there are multiple answers for this question, output the one appearing last in the 2D-array. There is always at least one answer.

Example 1:

Input: [[1,2], [1,3], [2,3]] Output: [2,3] Explanation: Original tree will be like this: 1 / \ 2 - 3

Example 2:

Input: [[1,2], [1,3], [3,1]] Output: [3,1] Explanation: Original tree will be like this: 1 / \\ 2 3

Note:

The size of the input 2D-array will be between 1 and 1000.

Every integer represented in the 2D-array will be between 1 and 2000.

```    class Union{
int[] id;
int[] sz;

Union(int n){
id = new int[n];
sz = new int[n];
for (int i = 0; i < n; ++i) {
id[i] = i;
}
Arrays.fill(sz, 1);
}

int find(int i) {
while (i != id[i]) {
i = id[i];
}
return i;
}

boolean same(int i, int j) {
return find(i) == find(j);
}

void union(int i, int j) {
int p = find(i);
int q = find(j);
if (p == q) return;

if (sz[p] > sz[q]) {
id[q] = p;
sz[p] += sz[q];
}
else {
id[p] = q;
sz[q] += sz[p];
}
}
}

public int[] findRedundantConnection(int[][] edges) {
int n = edges.length;
Union union = new Union(2000 + 16);
for (int i = 0; i < n; ++i) {
if (union.same(edges[i][0], edges[i][1])) return new int[] {edges[i][0], edges[i][1]};
else {
union.union(edges[i][0], edges[i][1]);
}
}
return new int[] {-1,-1};
}      ```

98 篇文章33 人订阅

0 条评论

## 相关文章

2943

2176

2038

2037

671

964

### python函数基础字符串操作numpy 和list互相转换

list 转 numpy np.array(a) ndarray 转 list a.tolist() 写入文件必须是字符

1101

3284

3264

### LeetCode75.颜色分类

这道题两种做法，一种是用计数排序，因为告诉了你只有3种数字，所以直接创建一个长度为3的数组arr，然后遍历一遍原数组，每出现一次某个数，arr对应位置的值...

602