Maximum Removable Edges - Explanation and Solution

Problem

You are given an undirected graph with n nodes and three types of edges:

• Type 1: Traversible by Alice only.
• Type 2: Traversible by Bob only.
• Type 3: Traversible by both Alice and Bob.

Given edges array where edges[i] = [type_i, u_i, v_i], find the maximum number of edges you can remove such that after removing them, both Alice and Bob can fully traverse the graph. Return the maximum number of edges that can be removed or -1 if Alice and Bob cannot fully traverse the graph.

Naive Approach

The most basic approach would be to try every possible combination of edge removals and, for each combination, check if both Alice and Bob can fully traverse the graph. This is a brute-force strategy.

1. Generate all subsets of edges: Iterate through all possible subsets of the given edges.
2. Check connectivity: For each subset (representing edges to keep), perform a Depth First Search (DFS) or Breadth First Search (BFS) for Alice's traversable edges and Bob's traversable edges separately, starting from an arbitrary node. If either cannot reach all nodes, discard the subset.
3. Maximize removal: Keep track of the maximum number of edges that can be removed while maintaining full traversal for both Alice and Bob.

Complexity:

• Time: O(2^E * (V + E)), where E is the number of edges and V is the number of vertices. The 2^E comes from generating all subsets. The (V+E) comes from the DFS/BFS operation to determine connectivity.
• Space: O(V + E) due to the graph representation in memory during each iteration. The size of the recursion stack can be O(V) in the worst case for DFS.

Optimal Solution

The optimal solution utilizes the concept of Disjoint Set Union (DSU) (also known as Union-Find) to efficiently determine connected components for Alice and Bob.

1. Type 3 Edges First: Process type 3 edges first. These edges are crucial because they connect components for both Alice and Bob simultaneously.
2. Alice-Specific and Bob-Specific Edges: Then, process type 1 (Alice-only) and type 2 (Bob-only) edges separately, adding them to the DSU structures.
3. Connectivity Check: After adding edges, check if Alice and Bob can each traverse the entire graph. If not, it's impossible to fully traverse, and return -1.
4. Count Removable Edges: The maximum number of removable edges will be the total edges minus the edges needed to connect all the nodes for both Alice and Bob.

Algorithm:

1. Initialize DSU data structures for Alice and Bob, each with n nodes.
2. Iterate through edges and process type 3 edges:
   • If adding an edge merges two disjoint sets for Alice, union them in Alice's DSU.
   • If adding an edge merges two disjoint sets for Bob, union them in Bob's DSU.
   • Increment the count of kept edges.
3. Iterate through edges again and process type 1 (Alice-only) edges:
   • If adding an edge merges two disjoint sets for Alice, union them in Alice's DSU.
   • Increment the count of kept edges.
4. Iterate through edges again and process type 2 (Bob-only) edges:
   • If adding an edge merges two disjoint sets for Bob, union them in Bob's DSU.
   • Increment the count of kept edges.
5. Check if Alice and Bob can fully traverse the graph:
   • If the number of connected components for Alice's DSU is not 1, return -1.
   • If the number of connected components for Bob's DSU is not 1, return -1.
6. Return the number of removed edges: total_edges - kept_edges

Code (Python):

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

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

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x != root_y:
            if self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            elif self.rank[root_x] > self.rank[root_y]:
                self.parent[root_y] = root_x
            else:
                self.parent[root_y] = root_x
                self.rank[root_x] += 1
            return True
        return False

def max_removable_edges(n: int, edges: list[list[int]]) -> int:
    alice_dsu = DSU(n)
    bob_dsu = DSU(n)

    kept_edges = 0
    total_edges = len(edges)

    # Process type 3 edges first
    for type, u, v in edges:
        if type == 3:
            if alice_dsu.union(u - 1, v - 1):
                bob_dsu.union(u - 1, v - 1)
                kept_edges += 1

    # Process type 1 edges (Alice-only)
    for type, u, v in edges:
        if type == 1:
            if alice_dsu.union(u - 1, v - 1):
                kept_edges += 1

    # Process type 2 edges (Bob-only)
    for type, u, v in edges:
        if type == 2:
            if bob_dsu.union(u - 1, v - 1):
                kept_edges += 1

    # Check if Alice and Bob can fully traverse
    alice_components = 0
    bob_components = 0

    for i in range(n):
        if alice_dsu.find(i) == i:
            alice_components += 1
        if bob_dsu.find(i) == i:
            bob_components += 1

    if alice_components != 1 or bob_components != 1:
        return -1

    return total_edges - kept_edges

Complexity:

• Time: O(E * α(N)), where E is the number of edges, N is the number of nodes, and α is the inverse Ackermann function, which grows extremely slowly and can be considered almost constant for practical input sizes. The dominant operations are the find and union operations of the DSU, which have near-constant time complexity with path compression and union by rank.
• Space: O(N) to store the parent and rank arrays in the DSU data structures.

Edge Cases:

• Disconnected Graph: If the initial graph (even with all type 3 edges) is disconnected for either Alice or Bob, the algorithm correctly returns -1.
• Single Node: If n is 1, any number of edges can be removed since it is already fully traversed. The DSU implementation handles this case without issue.
• No Edges: If edges is empty, then if n is 1 the return value is 0. If n is greater than 1, the return value is -1.
• Duplicate Edges: The problem description states that all tuples (type_i, u_i, v_i) are distinct. Therefore, you don't need to worry about this case.