Code Implementation

class DSU:
    def __init__(self, n):
        self.parent = list(range(n+1))
        self.rank = [0]*(n+1)
        self.components = n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        if xr == yr:
            return False
        if self.rank[xr] < self.rank[yr]:
            self.parent[xr] = yr
        elif self.rank[xr] > self.rank[yr]:
            self.parent[yr] = xr
        else:
            self.parent[yr] = xr
            self.rank[xr] += 1
        self.components -= 1
        return True

class Solution:
    def maxNumEdgesToRemove(self, n, edges):
        alice = DSU(n)
        bob = DSU(n)
        res = 0

        # Type 3 edges first
        for t,u,v in edges:
            if t == 3:
                merged_a = alice.union(u,v)
                merged_b = bob.union(u,v)
                if not (merged_a or merged_b):
                    res += 1

        # Type 1 (Alice only)
        for t,u,v in edges:
            if t == 1:
                if not alice.union(u,v):
                    res += 1

        # Type 2 (Bob only)
        for t,u,v in edges:
            if t == 2:
                if not bob.union(u,v):
                    res += 1

        if alice.components > 1 or bob.components > 1:
            return -1
        return res
      

class DSU {
public:
    vector<int> parent, rank;
    int components;
    DSU(int n) : parent(n+1), rank(n+1,0), components(n) {
        for (int i=0; i<=n; ++i) parent[i]=i;
    }
    int find(int x) {
        if (parent[x]!=x) parent[x]=find(parent[x]);
        return parent[x];
    }
    bool unite(int x, int y) {
        int xr=find(x), yr=find(y);
        if (xr==yr) return false;
        if (rank[xr]<rank[yr]) parent[xr]=yr;
        else if (rank[xr]>rank[yr]) parent[yr]=xr;
        else {parent[yr]=xr; rank[xr]++;}
        components--;
        return true;
    }
};

class Solution {
public:
    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
        DSU alice(n), bob(n);
        int res=0;
        // Type 3 first
        for (auto& e: edges)
            if (e[0]==3) {
                bool a = alice.unite(e[1],e[2]);
                bool b = bob.unite(e[1],e[2]);
                if (!a && !b) res++;
            }
        // Type 1
        for (auto& e: edges)
            if (e[0]==1)
                if (!alice.unite(e[1],e[2])) res++;
        // Type 2
        for (auto& e: edges)
            if (e[0]==2)
                if (!bob.unite(e[1],e[2])) res++;
        if (alice.components>1 || bob.components>1) return -1;
        return res;
    }
};
      

class DSU {
    int[] parent, rank;
    int components;
    DSU(int n) {
        parent = new int[n+1];
        rank = new int[n+1];
        components = n;
        for (int i=0; i<=n; ++i) parent[i]=i;
    }
    int find(int x) {
        if (parent[x]!=x) parent[x]=find(parent[x]);
        return parent[x];
    }
    boolean union(int x, int y) {
        int xr=find(x), yr=find(y);
        if (xr==yr) return false;
        if (rank[xr]<rank[yr]) parent[xr]=yr;
        else if (rank[xr]>rank[yr]) parent[yr]=xr;
        else {parent[yr]=xr; rank[xr]++;}
        components--;
        return true;
    }
}

class Solution {
    public int maxNumEdgesToRemove(int n, int[][] edges) {
        DSU alice = new DSU(n), bob = new DSU(n);
        int res = 0;
        // Type 3
        for (int[] e: edges)
            if (e[0]==3) {
                boolean a = alice.union(e[1],e[2]);
                boolean b = bob.union(e[1],e[2]);
                if (!a && !b) res++;
            }
        // Type 1
        for (int[] e: edges)
            if (e[0]==1)
                if (!alice.union(e[1],e[2])) res++;
        // Type 2
        for (int[] e: edges)
            if (e[0]==2)
                if (!bob.union(e[1],e[2])) res++;
        if (alice.components>1 || bob.components>1) return -1;
        return res;
    }
}
      

class DSU {
    constructor(n) {
        this.parent = Array(n+1).fill(0).map((_,i)=>i);
        this.rank = Array(n+1).fill(0);
        this.components = n;
    }
    find(x) {
        if (this.parent[x]!=x) this.parent[x]=this.find(this.parent[x]);
        return this.parent[x];
    }
    union(x,y) {
        let xr=this.find(x), yr=this.find(y);
        if (xr==yr) return false;
        if (this.rank[xr]<this.rank[yr]) this.parent[xr]=yr;
        else if (this.rank[xr]>this.rank[yr]) this.parent[yr]=xr;
        else {this.parent[yr]=xr; this.rank[xr]++;}
        this.components--;
        return true;
    }
}

var maxNumEdgesToRemove = function(n, edges) {
    let alice = new DSU(n), bob = new DSU(n), res = 0;
    // Type 3
    for (let [t,u,v] of edges)
        if (t==3) {
            let a=alice.union(u,v), b=bob.union(u,v);
            if (!a && !b) res++;
        }
    // Type 1
    for (let [t,u,v] of edges)
        if (t==1)
            if (!alice.union(u,v)) res++;
    // Type 2
    for (let [t,u,v] of edges)
        if (t==2)
            if (!bob.union(u,v)) res++;
    if (alice.components>1 || bob.components>1) return -1;
    return res;
};
      

Problem Description

You are given an undirected graph with n nodes, labeled from 1 to n. There are three types of edges:

• Type 1: Can only be traversed by Alice.
• Type 2: Can only be traversed by Bob.
• Type 3: Can be traversed by both Alice and Bob.

Your task is to remove the maximum number of edges from the graph so that the graph remains fully traversable for both Alice and Bob. This means both Alice and Bob must be able to reach every node from any starting point, using the edges available to them.

If it's not possible for both Alice and Bob to traverse the entire graph after removing edges, return -1.

Key constraints:

• Each edge can be used at most once (no duplicates in the final answer).
• Only one valid solution is required.
• Do not reuse elements or edges after removal.

Thought Process

At first glance, you might consider trying all possible combinations of edges to remove, checking each time if both Alice and Bob can still traverse the entire graph. However, this brute-force approach is not practical, especially as the number of possible edge combinations grows exponentially with the number of edges.

Instead, notice that the problem is about keeping the graph connected for two different "users" (Alice and Bob), each with their own set of usable edges, but with some overlap (type 3 edges). The goal is to maximize the number of removable edges, which means we want to keep only the essential edges that maintain connectivity for both Alice and Bob.

This leads us to think about minimum spanning trees (MSTs) and the use of Disjoint Set Union (DSU) data structures, which efficiently track connected components in a graph. By trying to add edges in a specific order (prioritizing shared edges), we can ensure that we only keep necessary edges and count the rest as removable.

Solution Approach

The solution uses the Disjoint Set Union (DSU) data structure to efficiently check and merge connected components for both Alice and Bob. The approach is as follows:

1. Initialize two DSU structures: One for Alice and one for Bob, each representing the connectivity of the graph for their respective edge types.
2. Process type 3 edges first: These edges are valuable because they help both Alice and Bob. For each type 3 edge, try to add it to both DSUs. If it does not connect any new nodes in either DSU (i.e., it forms a cycle in both), it is redundant and can be removed.
3. Process type 1 and type 2 edges:
   • Type 1 edges are only useful for Alice, so add them to Alice's DSU. If the edge is redundant (already connected), count it as removable.
   • Type 2 edges are only useful for Bob, so add them to Bob's DSU. If the edge is redundant, count it as removable.
4. Check full connectivity: After processing all edges, check if both Alice and Bob have a single connected component (i.e., they can each reach all nodes). If not, return -1 because it's impossible to keep the graph fully traversable for both.
5. Return the result: The answer is the count of redundant (removable) edges.

Why DSU? DSU allows us to efficiently merge components and check if two nodes are already connected, which is crucial for avoiding cycles and ensuring minimal edge usage.

Example Walkthrough

Let's walk through an example:

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

1. Type 3 edges: [3,1,2] and [3,2,3]
   • Add [3,1,2] to both Alice and Bob DSUs. They now connect 1-2.
   • Add [3,2,3] to both DSUs. They now connect 1-2-3.
2. Type 1 edges: [1,1,3], [1,2,4], [1,1,2]
   • [1,1,3]: In Alice's DSU, 1 and 3 are already connected (via type 3), so this is redundant and can be removed.
   • [1,2,4]: Connects 4 to the main component in Alice's DSU.
   • [1,1,2]: 1 and 2 are already connected, so this is redundant and can be removed.
3. Type 2 edge: [2,3,4]
   • Connects 4 to the main component in Bob's DSU.
4. Final check: Both Alice and Bob can reach all nodes. The number of removable edges is 2 ([1,1,3] and [1,1,2]).

Output: 2

Time and Space Complexity

• Brute-force approach: Would require checking all subsets of edges, leading to exponential time: O(2^E) where E is the number of edges. This is infeasible for large inputs.
• Optimized DSU approach:
  • Time complexity: Each find and union operation is nearly constant time due to path compression and union by rank, so overall O(E * α(N)), where α is the inverse Ackermann function (very slow-growing).
  • Space complexity: O(N) for the DSU structures (parent and rank arrays).

Summary

The problem asks us to maximize the number of removable edges while keeping the graph fully traversable for both Alice and Bob. By using the Disjoint Set Union (DSU) data structure and prioritizing shared edges (type 3), we efficiently determine which edges are essential and which are redundant. This approach ensures both users can traverse the entire graph, and the solution is both elegant and efficient, leveraging classic graph connectivity techniques.