Redundant Connection II

LeetCode Q 685 - Redundant Connection II

In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.

The given input is a directed graph that started as a rooted tree with N nodes (with distinct values 1, 2, …, N), with one additional directed 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] that represents a directed edge connecting nodes u and v, where u is a parent of child v.

Return an edge that can be removed so that the resulting graph is a rooted tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array.

Example 1:
Input: [[1,2], [1,3], [2,3]]
Output: [2,3]

Example 2:
Input: [[1,2], [2,3], [3,4], [4,1], [1,5]]
Output: [4,1]

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 : Disjoint Set / Union Find

1. what is a rooted tree?
   In a rooted tree, the parent of a vertex is the vertex connected to it on the path to the root; every vertex except the root has a unique parent. A child of a vertex v is a vertex of which v is the parent. A descendant of any vertex v is any vertex which is either the child of v or is (recursively) the descendant of any of the children of v. A sibling to a vertex v is any other vertex on the tree which has the same parent as v. The root is an external vertex if it has precisely one child. A leaf is different from the root.

2. There are 3 cases, where the cycle has redundante edges.

   • There is a cycle.
   • A node has two parents.
   • A node has two parents and one edge of this node introduces a cycle.
     These cases are shown as follows. We can eliminate reduanduncy like this.

• For case 1, we just remove the last edge introducing a cycle.
• For case 2, we delete one edge of that node. That edge is the last one causing multiple parents issue.
• For case 3, we delete one edge of that node. That edge is the first one causing multiple parents issue.

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[] findRedundantDirectedConnection(int[][] edges) {

  UnionFindSet ufs = new UnionFindSet(edges.length + 1);
  int[] cand1 = null, cand2 = null;
  
  for (int[] edge: edges) {
    int p1 = ufs.find(edge[0]), p2 = ufs.find(edge[1]);
    if (p1 != p2) {
      if (p2 != edge[1]) //record the last edge which results  in "multiple parents" issue
        cand1 = edge;
      else
        ufs.union(edge[1], edge[0]); // note the sequence, let edge[0] become the parent of edge[1]; 
    } else { // current edge causes a cycle
      cand2 = edge;
    }
  }

  if (cand1 == null) return cand2;
  if (cand2 == null) return cand1;

  // If both issues present, then the answer should be the first edge which results in "multiple parents" issue
  // Could use map to skip this pass, but will use more memory.
  for (int[] edge: edges) {
    if (edge[1] == cand1[1])
      return edge;
  }

  return null;
}