LeetCode 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  2
     ^    |
     |    v
     4 

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.

タイトルリンク:https://leetcode.com/problems/redundant-connection-ii/
题目分析:简単な问题、题目は1本の合法的な根の木が1本の辺を付け加えたと言うことがあって、だから直接1つの図に木を判断するより少し简単で、2种类の情况に分けます
1)入度が0の点が存在する:削除するのは必ず1つの入度が2の点のある入辺であることを得やすくて、しかも削除した後に連通を保証しなければならなくて、連通性は利用してそして採集して判断することができる
2)入度が0の点は存在しない:この場合はもっと簡単で、根は必然的に入度が1の点であり、しかもこの点の出度が0でない限り、必然的に木の根とすることができる.
1 msで99.48%を破った

class Solution {
    
    public int[] fa;
    
    public int find(int x) {
        if (x == fa[x]) {
            return x;
        }
        fa[x] = find(fa[x]);
        return fa[x];
    }
    
    public void union(int x, int y) {
        int r1 = find(x);
        int r2 = find(y);
        if (r1 != r2) {
            fa[r2] = r1;
        }
    }
    
    public boolean isConnect(int pos, int n, int[][] edges) {
        fa = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            fa[i] = i;
        }
        for (int i = 0; i < n; i++) {
            if (pos == i) {
                continue;
            }
            union(edges[i][0], edges[i][1]);
        }
        int rt = find(1);
        for (int i = 2; i <= n; i++) {
            if (find(i) != rt) {
                return false;
            }
        }
        return true;
    }
    
    public int[] findRedundantDirectedConnection(int[][] edges) {
        int n = edges.length;
        int[] inDegree = new int[n + 1];
        int[] outDegree = new int[n + 1];
        for (int i = 0; i < n; i++) {
            inDegree[edges[i][1]]++;
            outDegree[edges[i][0]]++;
        }
        int rt = -1;
        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == 0) {
                rt = i;
                break;
            }
        }
        if (rt != -1) {
            for (int i = n - 1; i >= 0; i--) {
                if (inDegree[edges[i][1]] == 2 && isConnect(i, n, edges)) {
                    return edges[i];
                }
            }
        } else {
            for (int i = n - 1; i >= 0; i--) {
                if (inDegree[edges[i][1]] == 1 && outDegree[edges[i][1]] > 0) {
                    return edges[i];
                }
            }
        }
        
        return new int[2];
    }
}