LWC 51：684. Redundant Connection
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};
}