685. Redundant Connection II

Description

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]
Explanation: The given directed graph will be like this:

image.png

Example 2:

Input: [[1,2], [2,3], [3,4], [4,1], [1,5]]
Output: [4,1]
Explanation: The given directed graph will be like this:

image.png

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

Test cases:

[[1,2], [2,3], [3,4], [4,1], [1,5]]

Solution

Union-Find, O(n), S(n)

This problem is very similar to "Redundant Connection". But the description on the parent/child relationships is much better clarified.

There are two cases for the tree structure to be invalid.

1. A node having two parents;
   including corner case: e.g. [[4,2],[1,5],[5,2],[5,3],[2,4]]
2. A circle exists

If we can remove exactly 1 edge to achieve the tree structure, a single node can have at most two parents. So my solution works in two steps.

1. Check whether there is a node having two parents.
   If so, store them as candidates A and B, and set the second edge invalid.
2. Perform normal union find.
   • If the tree is now valid
     - simply return candidate B
   • else if candidates not existing
     - we find a circle, return current edge;
   • else
     - remove candidate A instead of B.

Other explain

1. There is a loop in the graph, and no vertex has more than 1 parent.
   Example:
   Input: [[1,2], [2,3], [3,4], [4,1], [1,5]]
   Output: [4,1]

   
   0_1506493498612_drawing2.jpg

   In this case, you can simply output the edge in the loop that occurs last.
   Union-find can be used to check whether an directed graph contains a cycle or not. At first, every vertex is an independent subset. For each edge, join the subsets that are on both sides of the edge. If both the vertices are in the same subset, a cycle is found.

2. A vertex has more than 1 parent, but there isn't a loop in the graph.
   Example:
   Input: [[1,2], [1,3], [2,3]]
   Output: [2,3]

   
   0_1506493289378_drawing 1.jpg

   This case is also easy. You can just return the last edge that changes the tree into a graph. You can use an array of booleans to indicate whether a vertex has already got a parent.

3. A vertex has more than 1 parent, and is part of a loop.
   Example:
   Input: [[2,1], [3,1], [4,2], [1,4]]
   Output: [2,1]

   
   0_1506494193813_drawing3.jpg

   Case 3 is a mixture of case 1 and case 2. If you detect both cases, do the following:
   a. Find the vertex that has multiple parents. It is obvious that this vertex is also in the loop. In the example above, node 1 is what we are looking for.
   b. Starting from this vertex, use DFS to find the last edge that forms the cycle.
   c. Return this edge. In the example above, it is (2, 1).

class Solution {
    public int[] findRedundantDirectedConnection(int[][] edges) {
        int n = edges.length;
        int[] candidate1 = {-1, -1};
        int[] candidate2 = {-1, -1};
        int[] parent = new int[n + 1];  // parent[i] = j means j is parent of i
        
        for (int[] edge : edges) {
            int from = edge[0];
            int to = edge[1];
            if (parent[to] > 0) {   // duplicate parents
                candidate1 = new int[] {parent[to], to};
                candidate2 = new int[] {from, to};  // copy value
                edge[1] = -1;   // set this edge invalid
                break;
            } else {
                parent[to] = from;
            }
        }
        // prepare for union find, clear parent array
        Arrays.fill(parent, -1);
        
        for (int[] edge : edges) {
            if (edge[1] < 0) {  // skip invalid edge
                continue;
            }
            
            int i = edge[0];
            int j = edge[1];
            int iset = find(parent, i);
            int jset = find(parent, j);
            
            if (iset != jset) {
                union(parent, iset, jset);
            } else {
                if (candidate1[0] < 0) {
                    return edge;
                } else {
                    return candidate1;
                }
            }
        }
        
        return candidate2;
    }
    
    private int find(int[] parent, int i) {
        if (parent[i] == -1) {
            return i;
        }
        parent[i] = find(parent, parent[i]);
        return parent[i];
    } 
    
    private void union(int[] parent, int iset, int jset) {
        parent[iset] = jset;
    }
}