We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Remove Max Number of Edges to Keep Graph Fully Traversable

Difficulty: Hard

Problem Description

Alice and Bob have an undirected graph of n nodes and three types of edges: Type 1 (traversable by Alice only), Type 2 (traversable by Bob only), and Type 3 (traversable by both). Given an array of edges representing the graph, find the maximum number of edges you can remove while still allowing both Alice and Bob to fully traverse the graph. If it's impossible for both to fully traverse the graph, return -1.

Key Insights

  • Graph Traversability: Both Alice and Bob must be able to reach all nodes starting from any node.
  • Edge Types: Type 3 edges are critical since they can be traversed by both. They should be prioritized for keeping.
  • Union-Find Structure: Use the Union-Find (Disjoint Set Union) data structure to manage connectivity and efficiently check if all nodes are reachable.
  • Maximizing Removals: Count how many edges can be removed while maintaining full connectivity for both Alice and Bob.

Space and Time Complexity

Time Complexity: O(E * α(N)), where E is the number of edges and α is the inverse Ackermann function, which grows very slowly.
Space Complexity: O(N), for storing the parent and rank of nodes in the Union-Find structure.

Solution

To solve this problem, we will use a Union-Find (Disjoint Set Union) data structure to manage the connectivity of the graph. The solution involves the following steps:

  1. Initialize Union-Find structures for both Alice and Bob.
  2. Process the edges in a specific order: First, include all Type 3 edges (both can traverse), then Type 1 edges (only Alice), and finally Type 2 edges (only Bob).
  3. Union the nodes based on the edge type being processed to build two separate connectivity trees for Alice and Bob.
  4. Check if both Alice and Bob can reach all nodes from their respective starting points after processing all edges.
  5. Count the removable edges by subtracting the edges used for maintaining connectivity from the total edges.

Code Solutions

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [1] * size

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

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)
        if root_u != root_v:
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            elif self.rank[root_u] < self.rank[root_v]:
                self.parent[root_u] = root_v
            else:
                self.parent[root_v] = root_u
                self.rank[root_u] += 1

def maxEdgesToRemove(n, edges):
    uf_alice = UnionFind(n + 1)  # Union-Find for Alice
    uf_bob = UnionFind(n + 1)    # Union-Find for Bob
    type3_count = 0

    for edge in edges:
        if edge[0] == 3:
            uf_alice.union(edge[1], edge[2])
            uf_bob.union(edge[1], edge[2])
            type3_count += 1

    for edge in edges:
        if edge[0] == 1:
            uf_alice.union(edge[1], edge[2])
        elif edge[0] == 2:
            uf_bob.union(edge[1], edge[2])

    # Check if both can reach all nodes
    alice_root = uf_alice.find(1)
    bob_root = uf_bob.find(1)
    for i in range(1, n + 1):
        if uf_alice.find(i) != alice_root or uf_bob.find(i) != bob_root:
            return -1

    # Count removable edges
    removable_edges = len(edges) - (type3_count + (n - 1))
    return removable_edges
← Back to All Questions