How to Remove the Most Edges While Keeping a Graph Fully Traversable for Alice and Bob

Problem Statement

Alice and Bob share an undirected graph with n vertices and a list of edges. Each edge is of one of three types:

Type 1: can be traversed only by Alice.

Type 2: can be traversed only by Bob.

Type 3: can be traversed by both.

The goal is to remove as many edges as possible while still ensuring that both Alice and Bob can reach every vertex (i.e., the graph remains fully traversable for each of them). If it is impossible for either to traverse the whole graph, return -1. Otherwise, return the maximum number of removable edges.

Solution Overview

The problem can be solved efficiently with two disjoint‑set (Union‑Find) structures—one for Alice and one for Bob.

Process all type 3 edges first because they benefit both users. For each such edge, attempt to union the endpoints in Alice’s Union‑Find; if the union succeeds, also union the same edge in Bob’s structure. If the endpoints are already connected, the edge is redundant and can be removed (increment the answer counter).

Next, handle type 1 edges (Alice‑only). Try to union the endpoints in Alice’s Union‑Find; if the union fails (already connected), the edge is redundant and can be removed.

Then handle type 2 edges (Bob‑only) analogously using Bob’s Union‑Find.

After processing all edges, verify that both Union‑Find structures have exactly one connected component ( cnt == 1). If not, the graph cannot be fully traversed by Alice or Bob, so return -1. Otherwise, return the accumulated count of removed edges.

This approach guarantees the maximum number of deletions because any edge that does not contribute to connecting new components is unnecessary for full traversal.

Complexity Analysis

Both Union‑Find operations run in near‑constant amortized time ( α(n), the inverse Ackermann function). Therefore, the overall time complexity is O(m·α(n)), where m is the number of edges, and the memory usage is O(n) for the two parent arrays.

Reference Implementation (Java)

public int maxNumEdgesToRemove(int n, int[][] edges) {
    // vertices are 1‑based; create UnionFind with n+1 size
    UnionFind ufa = new UnionFind(n + 1);
    UnionFind ufb = new UnionFind(n + 1);
    int ans = 0; // number of removed edges

    // First pass: handle type 3 (shared) edges
    for (int[] edge : edges) {
        if (edge[0] == 3) {
            if (ufa.union(edge[1], edge[2])) {
                ufb.union(edge[1], edge[2]);
            } else {
                ans++; // redundant shared edge
            }
        }
    }

    // Second pass: handle exclusive edges
    for (int[] edge : edges) {
        if (edge[0] == 1) { // Alice only
            if (!ufa.union(edge[1], edge[2])) {
                ans++; // redundant edge for Alice
            }
        } else if (edge[0] == 2) { // Bob only
            if (!ufb.union(edge[1], edge[2])) {
                ans++; // redundant edge for Bob
            }
        }
    }

    // If either graph is not fully connected, return -1
    if (ufa.cnt != 1 || ufb.cnt != 1) {
        return -1;
    }
    return ans;
}

private class UnionFind {
    int[] parent;
    int cnt; // number of connected components

    public UnionFind(int n) {
        cnt = n - 1; // because vertices are 1‑based
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    private int find(int x) {
        if (x != parent[x]) parent[x] = find(parent[x]);
        return parent[x];
    }

    public boolean union(int x, int y) {
        if (isConnected(x, y)) return false;
        int px = find(x);
        int py = find(y);
        parent[px] = py;
        cnt--;
        return true;
    }

    private boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
}

Examples

Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]] Output: 2 Explanation: Removing edges [1,1,2] and [1,1,3] still allows both Alice and Bob to traverse the entire graph. No other edge can be removed without breaking full traversal.

Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]] Output: 0 Explanation: Deleting any edge would prevent either Alice or Bob from reaching all vertices.

Constraints

1 ≤ n ≤ 10⁵

1 ≤ edges.length ≤ min(10⁵, 3·n·(n‑1)/2)

edges[i].length == 3

1 ≤ edges[i][0] ≤ 3

1 ≤ edges[i][1] < edges[i][2] ≤ n

All tuples (typeᵢ, uᵢ, vᵢ) are distinct.