1579. Remove Max Number of Edges to Keep Graph Fully Traversable

T: O(mn + mlogm), m is edges len, sort)
S: O(n)

can't only cal removed edges -> 有些會漏掉

so we cal minRequiredEdges to build a graph (the edge is able to union)

class Solution {
    private static final int ALICE = 1;
    private static final int BOB = 2;
    private static final int BOTH = 3;

    public int maxNumEdgesToRemove(int n, int[][] edges) {
        Arrays.sort(edges, (a, b) -> b[0] - a[0]);
        UnionFind alice = new UnionFind(n);
        UnionFind bob = new UnionFind(n);
        int minRequiredEdges = 0;

        for (int[] edge : edges) {
            int type = edge[0];
            if (type == BOTH) {
                boolean a = alice.union(edge[1], edge[2]); // use ||, need to run union first, 
                boolean b = bob.union(edge[1], edge[2]); // or one of these 2, is true, will immediately return true
                if (a || b) { // and not execute b
                    minRequiredEdges++;
                }
            } else if (type == ALICE) {
                if (alice.union(edge[1], edge[2])) {
                    minRequiredEdges++;
                }
            } else {
                if (bob.union(edge[1], edge[2])) {
                    minRequiredEdges++;
                }
            }
        }
        if (alice.isFullyConnected() && bob.isFullyConnected()) {
            return edges.length - minRequiredEdges;
        }
        return -1;
    }
}
class UnionFind {
    int[] parent;
    int count;

    UnionFind(int n) {
        parent = new int[n+1];
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
        }
        count = n;
    }
    public boolean union(int x, int y) {
        int i = find(x);
        int j = find(y);
        if (i != j) {
            parent[i] = j;
            count--;
            return true;
        }

        return false;
    }
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    public boolean isFullyConnected() {
        System.out.println("count:" + count);
        return count == 1;
    }
}

/**



add 3 first -> 

if is able to union -> means a nessasary union
add edges 

if both can fully connected ->
at last cal all edges - min nessasary edges = removed edges


if can't fully connected either, return -1

T: O(n + mlogm), m is edges len, sort)
S: O(n)
 */