Crack the Backend

Problem Statement

There are n nodes and a list of edges. Each edge has a type: 1 = only Alice can use it, 2 = only Bob can use it, 3 = both can use it. Alice and Bob each need to be able to traverse the entire graph (reach every node) using only their allowed edges. Remove the maximum number of edges so that both can still traverse the graph. Return the number of edges removed.

Key Observations

Two Union Finds: Maintain one UF for Alice (she can use type 1 and 3) and one for Bob (type 2 and 3). Greedy: Add type-3 edges first to both UFs (they help both); then add type-1 to Alice's UF and type-2 to Bob's UF. For each edge we "use" it if it connects two components in the relevant UF(s). We need both graphs to be connected (one component). Edges kept = edges used by Alice UF + edges used by Bob UF, but type-3 edges are shared (we count each type-3 at most once per UF). So: process type-3 first, add to both UFs when it merges in either; then type-1 for Alice, type-2 for Bob. Removed = total edges - edges_kept. If either graph is not connected, return -1 (problem guarantees solution).

Approach

High-level: UF alice, UF bob. Sort or process by type: first type 3 (add to both UFs if they merge), then type 1 for Alice, type 2 for Bob. kept = number of edges that were used (merged components). removed = total - kept. If alice or bob not connected return -1.

Steps: int[] pa = new int[n+1], pb = new int[n+1]; init; int used = 0; for (edge type 3) if union(pa,u,v) or union(pb,u,v) used++; for (edge type 1) if union(pa,u,v) used++; for (edge type 2) if union(pb,u,v) used++; if components(pa)>1 || components(pb)>1 return -1; return edges.length - used;

Implementation

Java

int find(int[] p, int x) { return p[x] == x ? x : (p[x] = find(p, p[x])); }
void union(int[] p, int a, int b) { p[find(p, a)] = find(p, b); }
int comp(int[] p) { int c = 0; for (int i = 1; i < p.length; i++) if (find(p, i) == i) c++; return c; }

public int maxNumEdgesToRemove(int n, int[][] edges) {
    int[] pa = new int[n+1], pb = new int[n+1];

    for (int i = 1; i <= n; i++) { pa[i] = i; pb[i] = i; }
    int used = 0;

    for (int[] e : edges)
    if (e[0] == 3 && find(pa, e[1]) != find(pa, e[2])) { union(pa, e[1], e[2]); union(pb, e[1], e[2]); used++; }
    for (int[] e : edges)
    if (e[0] == 1 && find(pa, e[1]) != find(pa, e[2])) { union(pa, e[1], e[2]); used++; }
    for (int[] e : edges)
    if (e[0] == 2 && find(pb, e[1]) != find(pb, e[2])) { union(pb, e[1], e[2]); used++; }
    if (comp(pa) != 1 || comp(pb) != 1) {
        return -1;
    }

    return edges.length - used;
}

Test Cases

Example 1

Input

n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[2,1,4]]

Expected

2

Explanation

Remove 2 edges so both can traverse.

Complexity Analysis

Time: O(n α(n)) ≈ O(n).
Space: O(n).

Follow-ups

Path compression + rank for optimal UF.