684. Redundant Connection

Version # 2 Union Find
The only tricky part here is how to initialize the UF instance
Notice that -> a valid tree has vertex + 1 edges, since we have 1 redundant edge here, we have #vertices = #edges
This principle can also be used for the DFS version

 96.86 %
class Solution {
    class UF {
private int[] id;
private int[] size;
public UF(int N) {
id = new int[N];
size = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
size[i] = 1;
}
}

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

public boolean union(int p, int q) {
int rootP = root(p);
int rootQ = root(q);
if (rootP == rootQ) {
return false;
}
if (size[rootP] < size[rootQ]) {
id[rootP] = rootQ;
size[rootQ] += size[rootP];
} else {
id[rootQ] = rootP;
size[rootP] += size[rootQ];
}
return true;
}

}

public int[] findRedundantConnection(int[][] edges) {
if (edges == null || edges.length == 0 || edges[0] == null || edges[0].length == 0) {
return null;
}
int N =edges.length;
UF uf = new UF(N);
for (int[] edge : edges) {
if (!uf.union(edge[0] - 1, edge[1] - 1)) {
return edge;
}
}
return null;
}
}

Version #1 DFS

Time O(n^2) Space O()
[WHEN DONT WE NEED BACKTRACKING]
Notice that the backtracking part -> visited.remove(curr) is not necessary
If we do visited.remove(curr), means we are assuming that there's another situation that curr can be reached from another path that linking start node and curr node
-> which means there are two paths between start & curr
-> Since we guarantee that there's no cycle before, the curr will never be reached from another previous node, so this remove is not necessary

 9.09 %

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
if (edges == null || edges.length == 0 || edges[0] == null || edges[0].length == 0) {
return null;
}
Map<Integer, Set<Integer>> graph = new HashMap<>();
for (int[] edge : edges) {
// [u, v] -> u < v
int curr = edge[0];
int target = edge[1];
if (dfs(graph, curr, target, new HashSet<>())) {
return edge;
}
if (!graph.containsKey(curr)) {
graph.put(curr, new HashSet<>());
}
if (!graph.containsKey(target)) {
graph.put(target, new HashSet<>());
}
graph.get(curr).add(target);
graph.get(target).add(curr);
}
return null;
}
private boolean dfs(Map<Integer, Set<Integer>> graph, int curr, int target, Set<Integer> visited) {
if (curr == target) {
return true;
}
visited.add(curr);
Set<Integer> neighbors = graph.get(curr);
if (neighbors != null) {
for (Integer neighbor : neighbors) {
if (!visited.contains(neighbor) && dfs(graph, neighbor, target, visited)) {
return true;
}
}
}
// visited.remove(curr);
return false;
}
}