Remove max number of edges to keep graph fully traversable

XXX. Max Number of Edges to Remove

Union-Find

Greedy

Problem Statement:

There are n nodes in an undirected graph, and the graph is given as an array edges where edges[i] = [type, u, v]:

• type == 1 denotes an edge that can only be used by Alice.
• type == 2 denotes an edge that can only be used by Bob.
• type == 3 denotes an edge that can be used by both Alice and Bob.

Return the maximum number of edges that can be removed while ensuring that Alice and Bob can each traverse the entire graph.

Algorithm:

The problem is solved using a double union-find structure to track connections for both Alice and Bob separately. The process involves:

1. Initialize union-find data structures for Alice and Bob with separate parent and size arrays.
2. Process edges of type 3 first, as these are shared by both Alice and Bob. Attempt to connect the nodes for both Alice and Bob, and count the number of edges successfully used.
3. Process edges of type 1 (Alice-only) and type 2 (Bob-only) separately, connecting nodes and counting successful edges.
4. After processing all edges, check if both Alice and Bob’s graphs are fully connected. If not, return -1. Otherwise, calculate the maximum number of removable edges as the total number of edges minus the edges used.

Complexity:

Time Complexity: O(E + V), where E is the number of edges and V is the number of nodes. Each edge is processed once, and the union-find operations are nearly constant due to path compression.
Space Complexity: O(V), for storing the parent and size arrays for both Alice and Bob.

Java Implementation:

class Solution {
    // Double union find
    public int maxNumEdgesToRemove(int n, int[][] edges) {
        // Union-Find structures for Alice and Bob
        int[] aliceParent = new int[n + 1], bobParent = new int[n + 1], aliceSize = new int[n + 1], bobSize = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            aliceParent[i] = i;
            bobParent[i] = i;
            aliceSize[i] = 1;
            bobSize[i] = 1;
        }

        int edgesRequired = 0;

        // Process type 3 edges first
        for (int[] edge : edges) if (edge[0] == 3) {
            if (union(edge[1], edge[2], aliceParent, aliceSize) | union(edge[1], edge[2], bobParent, bobSize)) edgesRequired++;
        }

        // Process type 1 and type 2 edges
        for (int[] edge : edges) if (edge[0] == 1) {
            if (union(edge[1], edge[2], aliceParent, aliceSize)) edgesRequired++;
        } else if (edge[0] == 2) {
            if (union(edge[1], edge[2], bobParent, bobSize)) edgesRequired++;
        }

        return (isConnected(aliceParent, n) && isConnected(bobParent, n)) ? edges.length - edgesRequired : -1;
    }

    // Find function with path compression
    private int find(int node, int[] parent) {
        if (parent[node] != node) parent[node] = find(parent[node], parent);
        return parent[node];
    }

    // Union function with size balancing
    private boolean union(int u, int v, int[] parent, int[] size) {
        int rootU = find(u, parent), rootV = find(v, parent);
        if (rootU == rootV) return false;
        if (size[rootU] > size[rootV]) {
            parent[rootV] = rootU;
            size[rootU] += size[rootV];
        } else {
            parent[rootU] = rootV;
            size[rootV] += size[rootU];
        }
        return true;
    }

    // Check if all nodes are connected
    private boolean isConnected(int[] parent, int n) {
        int root = find(1, parent);
        for (int i = 2; i <= n; i++) if (find(i, parent) != root) return false;
        return true;
    }
}