685.Redundant Connection II

1-Union Find

685. Redundant Connection II从前面的无向图升级到了有向图，对应的要求从原来的仅要求不形成环路升级到在不形成环路的基础上，拓扑必须要是一棵合法树，也就是每个点只能有一个父节点，例如[[2,1],[3,1]]这两条边虽然没有形成环路，但是 1 有两个父亲节点（2和3），因此不是一棵合法的树。

由于题目说明了输入只有一条不合法的边，因此首先可以统计一下这些边中是否存在某个点有两个父亲节点，假如有，则需要移除的边必定为连着这个点的两条边中的一条，通过上面 Union-find 的方法，可以判断出假如移除掉连着这个点的第一条边时，是否会形成回路。如果会，则说明需要移除第二条边，否则直接移除第一条边。

如果统计的结果中没有点含有两个父亲节点，那么可以直接通过第一题的方法直接找到形成回路的最后那条边。

http://wulc.me/2017/10/12/LeetCode%20%E8%A7%A3%E9%A2%98%E6%8A%A5%E5%91%8A\(684%EF%BC%8C685\)-%E5%B9%B6%E6%9F%A5%E9%9B%86%E4%BB%8B%E7%BB%8D%E5%8F%8A%E5%BA%94%E7%94%A8/

https://discuss.leetcode.com/topic/105087/share-my-solution-c

https://leetcode.com/problems/redundant-connection-ii/discuss/108045?page=1

综上，这个算法就有两步：

• 第一步，找到入度为2的点（当然，有可能不存在）
• 第二步，搜索图中是否存在环

• //if after remove can1,(continue) there are no cycle. we should return can1.

  //else we need to find one front of it; either is can2 of some one that forms a cycle

class Solution {
    public int[] findRedundantDirectedConnection(int[][] edges) {
        int[] can1 = {-1, -1};
        int[] can2 = {-1, -1};
        Map<Integer, Integer> roots = new HashMap<>();
        Map<Integer, Integer> parent = new HashMap<>();
        for(int[] edge : edges){
            //find if there are node have two parents. if so, we generate two candidates.
            if(parent.containsKey(edge[1])){
                can1[0] = edge[0];
                can1[1] = edge[1];

                can2[0] = parent.get(edge[1]);
                can2[1] = edge[1];

                //remove
                edge[1] = 0;
            }
            else{
                parent.put(edge[1], edge[0]);
            }
        }
        for(int[] edge : edges){
            roots.put(edge[0], -1);
            roots.put(edge[1], -1);
        }

        int[] ans = new int[2];
        //if after remove can1,(continue) there are no cycle. we should return can1.
        //else we need to find one front of it; either is can2 of some one that forms a cycle
        ans[0] = can1[0];
        ans[1] = can1[1];
        for(int[] edge : edges){
            if(edge[1] == 0){
                continue;
            }
            else{
                int root1 = find(roots, edge[0]);
                int root2 = find(roots, edge[1]);
                //If have cycle
                if(root1 == root2){
                    //if we 
                    if(can1[0] == -1){
                        ans[0] = edge[0];
                        ans[1] = edge[1];
                    }
                    else{
                        ans[0] = can2[0];
                        ans[1] = can2[1];
                    }
                    break;
                }
                else{
                    roots.put(root2, root1);
                }
            }
        }

        return ans;
    }
    public int find(Map<Integer, Integer> roots, Integer node){
        if(roots.get(node) == -1)
            return node;
        else{
            return find(roots, roots.get(node));
        }
    }
}