Redundant Connection II

Tree, Depth-first Search, Union Find, Graph

Hard

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 ofedges. Each element ofedgesis a pair[u, v]that represents adirectededge connecting nodesuandv, whereuis a parent of childv.

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:
  1
 / \
v   v
2-->3

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:
5 <- 1 -> 2
     ^    |
     |    v
     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.

Analysis

Redundant Connection 那道题给的是无向图，只需要删掉组成环的最后一条边即可，归根到底就是检测环就行了。而这道题给我们的是有向图，那么整个就复杂多了，因为有多种情况存在 via @Grandyang

From: @cherryljr/LeetCode/Redundant Connection II.java

本题中使得树 invalid 的情况总共有 1+2=3 种。

 *  Case 1:
 *      每个节点都只有 一个 父亲节点，但是形成了环。
 *      如：[1, 2], [2, 3], [3, 1]
 *      这种情况下，题目退化成 Redundant Connection，只需要使用 Union Find 寻找
 *      是因为哪条边形成了环，然后返回即可。
 *  Case 2.1:
 *      有某个节点存在 两个 父亲节点，但并没有形成环。(注意这里指的是有向图的环)
 *      如：[1, 2], [1, 3], [2, 3]
 *      这种情况下，我们需要删除最后一次遇到的形成环的边，即 [2, 3]
 *  Case 2.2：
 *      有某个节点存在 两个 父亲节点，并且形成了环。
 *      如：[2, 1], [3, 1], [4, 2], [1, 4]
 *      这种情况下，如果按找 Redundant Connection 中的做法就会出现错误，
 *      因为形成环的边会被判断成 [1, 4], 而就算删除了这条边，1 仍然两个父亲节点，这是错误的。

因此当我们遇到某个节点有 两个父亲节点 的情况时，我们需要删除的是：

• 如果没有环，删除 最后一次遇到 的 存在两个父亲的节点 的边；

• 如果有环，删除 环中 的 存在两个父亲的节点 的边。

Time complexity: O(nlog*n) ~ O(n)

Space complexity: O(n)

Solution

Union Find

Based on 李同学's:

class Solution {
    class UnionFind {
        int[] parent;
        int[] rank;
        int size;

        public UnionFind(int size) {
            this.size = size;
            parent = new int[size];
            rank = new int[size];

            for (int i = 0; i < size; i++) {
                parent[i] = i;
            }
        }

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

            return parent[x];
        }

        // return true if x, y has same parent
        public boolean union(int x, int y) {
            int xp = find(x);
            int yp = find(y);
            if (xp == yp) {
                return false;
            }
            if (rank[xp] > rank[yp]) {
                parent[yp] = xp;
            } else if (rank[xp] < rank[yp]) {
                parent[xp] = yp;
            } else {
                parent[yp] = xp;
                rank[xp]++;
            }
            return true;
        }
    }
    public int[] findRedundantDirectedConnection(int[][] edges) {
        HashSet<Integer> points = new HashSet<>();
        HashMap<Integer, Integer> parent = new HashMap<>();
        List<int[]> candidates = new ArrayList<>();

        for (int[] edge: edges) {
            int src = edge[0];
            int dst = edge[1];
            points.add(src);
            points.add(dst);
            if (!parent.containsKey(dst)) {
                parent.put(dst, src);
                continue;
            }

            // if a node has two parents, add to candidates list
            candidates.add(new int[] {parent.get(dst), dst});
            candidates.add(new int[] {src, dst});

            // invalidate the second edge
            edge[1] = -1;
        }

        UnionFind uf = new UnionFind(points.size());
        for (int[] edge: edges) {
            // skip invalidated edge
            if (edge[1] == -1) {
                continue;
            }

            int src = edge[0] - 1;
            int dst = edge[1] - 1;

            if (!uf.union(src, dst)) {

                // if we have invalidated the second edge
                // yet still have a cycle
                // we either just formed a cycle with this edge
                // or there still exists a node with two parents
                // which is the first edge stored in candidates.get(0)
                if (candidates.isEmpty()) {
                    return edge;
                }

                return candidates.get(0);
            }
        }

        // no cycle found, meaning the redundant edge 
        // is the second edge in the candidates 
        return candidates.get(1);
    }
}

Reference

https://www.youtube.com/watch?v=lnmJT5b4NlM&t=2s

http://zxi.mytechroad.com/blog/graph/leetcode-685-redundant-connection-ii/

https://github.com/cherryljr/LeetCode/blob/master/Redundant Connection II.java

http://www.cnblogs.com/grandyang/p/8445733.html