# 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)

```java
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)
 */
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/union-find/1579.-remove-max-number-of-edges-to-keep-graph-fully-traversable.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.