685. Redundant Connection II

class Solution {
    class DSU {
        int[] size;
        int[] root;
        public DSU(int n) {
            size = new int[n + 1];
            root = new int[n + 1];
            Arrays.fill(size, 1);
            for (int i = 0; i <= n; i++) {
                root[i] = i;
            }
        }
        
        public int find(int x) {
            if (root[x] != x) {
                root[x] = find(root[x]);
            }
            
            return root[x];
        }
        
        public boolean union(int x, int y) {
            int rootX = find(x), rootY = find(y);
            if (rootX == rootY) return false;
            if (size[rootX] < size[rootY]) {
                size[rootY] += size[rootX];
                root[rootX] = rootY;
            } else {
                size[rootX] += size[rootY];
                root[rootY] = rootX;
            }
            
            return true;
        }
    }
    
    public int[] detectCycle(int n, int[][] edges, int[] skipEdge) {
        DSU dsu = new DSU(n);
        for (int[] e : edges) {
            if (Arrays.equals(e, skipEdge)) continue;
            if (!dsu.union(e[0], e[1])) return e;
        }
        
        return null;
    }
    
    public int[] findRedundantDirectedConnection(int[][] edges) {
        int n = edges.length;
        int[] indegrees = new int[n + 1];
        int hasTwoIndegrees = -1;
        for (int[] e : edges) {
            indegrees[e[1]]++;
            if (indegrees[e[1]] == 2) {
                hasTwoIndegrees = e[1];
                break;
            }
        }
        
        if (hasTwoIndegrees == -1) return detectCycle(n, edges, null);
        for (int i = n - 1; i >= 0; i--) {
            if (edges[i][1] == hasTwoIndegrees) {
                if (detectCycle(n, edges, edges[i]) == null) return edges[i];
            }
        }
        
        return new int[0];
    }
}