684. 685. Redundant Connection, Redundant Connection II

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.

Update (2017-09-26):
We have overhauled the problem description + test cases and specified clearly the graph is an undirected graph. For the directedgraph follow up please see Redundant Connection II). We apologize for any inconvenience caused.

-----------------------
Union Find. DFS 也可以做，只是题意要求返回在原数组里最靠后的一位，所以UF更简单

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        int[] ids = new int[n + 1];
        int[] sizes = new int[n + 1];
        
        for (int i = 1; i <= n; i++) {
            ids[i] = i;
            sizes[i] = 1;
        }
        
        for (int[] e : edges) {
            int r1 = find(ids, e[0]);
            int r2 = find(ids, e[1]);
            if (r1 == r2) return e;
            
            union(r1,r2,ids,sizes);
        }
        
        return null;
    }
    
    private void union(int id1, int id2, int[] ids, int[] sizes) {
        if (sizes[id1] > sizes[id2]) {
            sizes[id1] += sizes[id2];
            ids[id2] = id1;
        }else {
            sizes[id2] += sizes[id1];
            ids[id1] = id2;
        }
    }
    
    private int find(int[] ids, int id) {
        while (ids[id] != id) {
            ids[id] = ids[ids[id]];
            id = ids[id];
        }
        
        return id;
    }
}

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]
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.

-----------------------

因为是tree ＋ 1个extra edge，所以分2种情况：

1. 所有的结点都有parent(包括root)。这有个环。

或

2. 有一个结点有2个parent指向。这里还可以分2种情况。

思路是先确定是哪种情况，2的话找出那2个parent的指向，然后断开第2个。进行正常的UF操作，如果碰到是2的情况，那说明先前存的第1个parent指向是extra edge。如果碰到的都是是1的情况，则当前的edge是多余。

如果没有相同的父节点，说明之前断开第2个edge是多余的（环被打断）

同样的，这题可以用DFS做，也得先preprocess

class Solution {
    public int[] findRedundantDirectedConnection(int[][] edges) {
        int n = edges.length;
        int[] ids = new int[n + 1];
        int[][] cands = new int[2][2];
        
        for (int[] e : edges) {            
            if (ids[e[1]] != 0) {
                cands[0] = new int[]{ids[e[1]], e[1]};
                cands[1] = new int[]{e[0], e[1]};
                e[0] = 0;
            }else {
                ids[e[1]] = e[0];    
            }
        }
        
        for (int i = 1; i <= n; i++) 
            ids[i] = i;
        
        for (int[] e : edges) {
            if (e[0] == 0) continue;
            int r1 = find(ids, e[0]);
            int r2 = e[1];
            if (r1 == r2) {
                if (cands[0][0] == 0) return e;
                return cands[0];
            }
            
            ids[r2] = r1;
        }
        
        return cands[1];
    }
    
    private int find(int[] ids, int id) {
        while (ids[id] != id) {
            ids[id] = ids[ids[id]];
            id = ids[id];
        }
        
        return id;
    }
}