BiruLyu
9/24/2017 - 3:19 PM

## 684. Redundant Connection(1st).cpp

``````public class Solution {
public int[] findRedundantConnection(int[][] edges) {
if (edges == null || edges.length < 1 || edges[0].length < 1) return new int[0];
int n = edges.length + 1;
UnionFind uf = new UnionFind(2010);
for (int[] e : edges) {
uf.make_set(e[0]);
uf.make_set(e[1]);
}
for (int[] e : edges) {
if (uf.find(e[0]) != uf.find(e[1])) {
uf.union(e[0], e[1]);
} else {
return e;
}
}
return new int[0];
}
}
class UnionFind {
private int[] parent;
private int[] size;
private int n, count;

public UnionFind (int n) {
this.n = n;
this.count = n;
parent = new int[n];
size = new int[n];
}

public void make_set(int x) {
parent[x] = x;
size[x] = 1;
}

public int find(int x) {
// if (parent[x] != x) {
//     parent[x] = find(parent[x]);
// }
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}

return x;
}

public void union(int x, int y) {
int parentX = find(x);
int parentY = find(y);
if (parentX != parentY) {
if (size[parentX] > size[parentY]) {
parent[parentY] = parentX;
size[parentX] += size[parentY];
} else {
parent[parentX] = parentY;
size[parentY] += size[parentX];
}
count--;
}
}

public int getCount() {
return count;
}
}``````
``````class Solution {
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
map<int, int> parent;
for (auto e : edges) {
if (parent.find(e[1]) != parent.end()) {
return e;
}
if (parent.find(e[0]) != parent.end()) {
if (parent[e[0]] == e[1])
return e;
}
parent[e[1]] = e[0];
}
set<int> root;
for (auto e : edges) {
if (root.find(e[1]) != root.end())
return e;
root.insert(e[0]);
}
return edges.back();
}
};``````