Redundant Connection

LeetCode Q 684 - Redundant Connection

In this problem, a tree is an undirected graph that is connected and has no cycles.
The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, …, N), with one additional edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.
The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] with u < v, that represents an undirected edge connecting nodes u and v.

Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. The answer edge [u, v] should be in the same format, with u < v.

Example 1: Input: [[1,2], [1,3], [2,3]] ; Output: [2,3]
Explanation: The given undirected graph will be like this:
  1
 / \
2 - 3
Example 2: Input: [[1,2], [2,3], [3,4], [1,4], [1,5]] ; Output: [1,4]
Explanation: The given undirected graph will be like this:
5 - 1 - 2
 | |
 4 - 3

Note:

• The size of the input 2D-array will be between 3 and 1000.
• Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.

Solution

Solution 1 : DFS

Time Complexity: O(n^2)

Code:

Set<Integer> seen = new HashSet<>();

public int[] findRedundantConnection(int[][] edges) {
  
  Map<Integer, List<Integer>> graph = new HashMap<>();

  for (int[] edge: edges) {
    seen.clear();
    if (!graph.containsKey(edge[0]) && 
        !graph.containsKey(edge[1]) && 
        hasCycle(graph, edge[0], edge[1]))
      return edge;
    graph.putIfAbsent(edge[0], new ArrayList<>());
    graph.get(edge[0]).add(edge[1]);
    graph.putIfAbsent(edge[1], new ArrayList<>());
    graph.get(edge[1]).add(edge[0]);
  }

  return null;
}

private boolean hasCycle (Map<Integer, List<Integer>> graph, int start, int end) {

  if (seen.contains(start)) return false;

  if (start == end) return true;

  if (!graph.containsKey(start)) return false;

  seen.add(start);
  List<Integer> nexts = graph.get(start);
  for (int next: nexts) {
    if (hasCycle(graph, next, end))
 	  return true;
  }

  return false;
}

Solution 2 : Disjoint Set / Union Find

Time Complexity: O(n)

Code:

class UnionFindSet {
  int[] parent;
  public UnionFindSet (int size) {
    this.parent = new int[size];
    for (int i = 0; i < size; i++)
      parent[i] = i;
  }
  public int find (int x) {
    int p = x;
    while (p != parent[p]) 
      p = parent[p];
    return p;
  }
  public void union (int x, int y) {
    int px = find(x), py = find(y);
    if (px != py) parent[px] = py;
  }
}

public int[] findRedundantConnection(int[][] edges) {

  UnionFindSet ufs = new UnionFindSet(edges.length + 1);

  for (int[] edge: edges) {
    if (ufs.find(edge[0]) == ufs.find(edge[1]))
      return edge;
    ufs.union(edge[0], edge[1]);
  }

  return null;
}