LeetCode Solutions Blog

Remove Max Number of Edges to Keep Graph Fully Traversable

Number: 1701

Difficulty: Hard

Paid? No

Problem Description

Given an undirected graph with n nodes and edges of three types (Alice-only, Bob-only, and common to both), remove the maximum number of redundant edges while ensuring that both Alice and Bob can traverse the entire graph (i.e. the graph remains connected for both users). If it’s impossible for both to traverse the entire graph, return -1.

Key Insights

Use the union-find (disjoint set union) data structure to efficiently manage connectivity.
Process type 3 (common) edges first since they benefit both Alice and Bob.
Then process type 1 (Alice-only) edges for Alice’s connectivity and type 2 (Bob-only) edges for Bob’s connectivity.
Count the edges that are actually used and subtract them from the total to get the maximum removals.
Finally, verify that both Alice’s and Bob’s graphs are fully connected.

Space and Time Complexity

Time Complexity: O(E * α(N)) where α is the inverse Ackermann function (almost constant) Space Complexity: O(N) for maintaining the union-find data structures

Solution

We approach the problem using two separate union-find structures – one for Alice and one for Bob. First, we process type 3 edges (usable by both) and union the nodes in both DSUs. Next, we process type 1 edges for Alice’s DSU and type 2 edges for Bob’s DSU. An edge that does not contribute to union (i.e. both nodes already connected) is redundant and can be removed. After processing all edges, we check if both DSUs have a single connected component. If yes, the total number of removable edges is (total edges - used edges); otherwise, return -1. The key idea is to maximize the sharing of edges between Alice and Bob by using the shared edges first.

Code Solutions

# Python solution using union-find

class DSU:
    def __init__(self, n):
        # parent pointer for each node (1-indexed)
        self.parent = list(range(n + 1))
        # Optionally track the number of connected components
        self.components = n

    def find(self, x):
        # Path compression
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        # Union by parent approach and return True if union performed
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX == rootY:
            return False
        self.parent[rootY] = rootX
        self.components -= 1
        return True

def maxNumEdgesToRemove(n, edges):
    # Initialize DSU for Alice and Bob
    dsuA = DSU(n)
    dsuB = DSU(n)
    usedEdges = 0
    
    # Process type 3 edges first (usable by both)
    for edge in edges:
        typeEdge, u, v = edge
        if typeEdge == 3:
            # If this edge connects two separate components in either DSU, use it in both
            if dsuA.union(u, v) | dsuB.union(u, v):
                usedEdges += 1
                
    # Process type 1 edges for Alice only
    for edge in edges:
        typeEdge, u, v = edge
        if typeEdge == 1:
            if dsuA.union(u, v):
                usedEdges += 1
    
    # Process type 2 edges for Bob only
    for edge in edges:
        typeEdge, u, v = edge
        if typeEdge == 2:
            if dsuB.union(u, v):
                usedEdges += 1
                
    # Check if both Graphs are fully traversable
    if dsuA.components != 1 or dsuB.components != 1:
        return -1
    
    # Maximum removable edges
    return len(edges) - usedEdges

# Example usage:
# n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
#print(maxNumEdgesToRemove(4, [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]))