Remove Max Number of Edges to Keep Graph Fully Traversable

Hard

Asked by:

79 views

Topics:

GraphsGreedy Algorithms

Alice and Bob have an undirected graph of n nodes and three types of edges:

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

Given an array edges where edges[i] = [type_i, u_i, v_i] represents a bidirectional edge of type type_i between nodes u_i and v_i, find the maximum number of edges you can remove so that after removing the edges, the graph can still be fully traversed by both Alice and Bob. The graph is fully traversed by Alice and Bob if starting from any node, they can reach all other nodes.

Return the maximum number of edges you can remove, or return -1 if Alice and Bob cannot fully traverse the graph.

Example 1:

Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
Output: 2
Explanation: If we remove the 2 edges [1,1,2] and [1,1,3]. The graph will still be fully traversable by Alice and Bob. Removing any additional edge will not make it so. So the maximum number of edges we can remove is 2.

Example 2:

Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]
Output: 0
Explanation: Notice that removing any edge will not make the graph fully traversable by Alice and Bob.

Example 3:

Input: n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]]
Output: -1
Explanation: In the current graph, Alice cannot reach node 4 from the other nodes. Likewise, Bob cannot reach 1. Therefore it's impossible to make the graph fully traversable.

Constraints:

1 <= n <= 10⁵
1 <= edges.length <= min(10⁵, 3 * n * (n - 1) / 2)
edges[i].length == 3
1 <= type_i <= 3
1 <= u_i < v_i <= n
All tuples (type_i, u_i, v_i) are distinct.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum number of nodes (n) and edges in the graph? I need to understand the scale of the input.
Can there be self-loops or duplicate edges in the input?
If it's impossible to make the graph fully traversable by both Alice and Bob, what should the function return?
Are the node labels guaranteed to be consecutive integers starting from 1, or could there be gaps in the numbering?
Can the 'type' of an edge be any value other than 1, 2, or 3? What is the meaning of the type of edge?

Brute Force Solution

Approach

The core idea of brute force here is to try out absolutely every combination of edges we could remove from the graph. For each of these combinations, we'll check if removing those edges still leaves the graph in a state where everyone can travel anywhere they need to go.

Here's how the algorithm would work step-by-step:

First, think about all possible combinations of edges that we could choose to remove.
Start by choosing to remove no edges, then one edge, then two edges, and so on, all the way up to removing nearly all of them.
For each specific combination of edges we decide to remove, build a new version of the graph without those edges.
Now, check if this new version of the graph is fully traversable for both types of users: those who require one set of roads and those who require another.
If the graph is fully traversable by both types of users, remember this combination and the number of edges that were removed.
After going through every single combination of edges, compare all the remembered combinations.
Select the combination that removed the most edges while still ensuring the graph remains fully traversable for both types of users. That's your answer!

Code Implementation

def remove_max_edges_brute_force(number_of_nodes, edges):    max_removed_edges = -1
    number_of_edges = len(edges)
    
    for i in range(1 << number_of_edges):
        edges_to_keep = []
        number_of_removed_edges = 0

        for j in range(number_of_edges):
            if (i >> j) & 1:
                edges_to_keep.append(edges[j])
            else:
                number_of_removed_edges += 1

        # Build the graph with the edges we want to keep
        graph_user_one = [[] for _ in range(number_of_nodes + 1)]
        graph_user_two = [[] for _ in range(number_of_nodes + 1)]
        graph_both_users = [[] for _ in range(number_of_nodes + 1)]

        for edge_type, node_one, node_two in edges_to_keep:
            if edge_type == 1:
                graph_user_one[node_one].append(node_two)
                graph_user_one[node_two].append(node_one)
                graph_both_users[node_one].append(node_two)
                graph_both_users[node_two].append(node_one)
            elif edge_type == 2:
                graph_user_two[node_one].append(node_two)
                graph_user_two[node_two].append(node_one)
                graph_both_users[node_one].append(node_two)
                graph_both_users[node_two].append(node_one)
            else:
                graph_both_users[node_one].append(node_two)
                graph_both_users[node_two].append(node_one)
                graph_user_one[node_one].append(node_two)
                graph_user_one[node_two].append(node_one)
                graph_user_two[node_one].append(node_two)
                graph_user_two[node_two].append(node_one)

        # Check if the graph is fully traversable for user one
        visited_user_one = [False] * (number_of_nodes + 1)
        def dfs_user_one(node):
            visited_user_one[node] = True
            for neighbor in graph_user_one[node]:
                if not visited_user_one[neighbor]:
                    dfs_user_one(neighbor)

        dfs_user_one(1)
        is_traversable_one = all(visited_user_one[i] for i in range(1, number_of_nodes + 1))

        # Check if the graph is fully traversable for user two
        visited_user_two = [False] * (number_of_nodes + 1)
        def dfs_user_two(node):
            visited_user_two[node] = True
            for neighbor in graph_user_two[node]:
                if not visited_user_two[neighbor]:
                    dfs_user_two(neighbor)

        dfs_user_two(1)
        is_traversable_two = all(visited_user_two[i] for i in range(1, number_of_nodes + 1))

        # If both users can fully traverse the graph, update the result
        if is_traversable_one and is_traversable_two:
            max_removed_edges = max(max_removed_edges, number_of_removed_edges)

    if max_removed_edges == -1:
        return -1
    else:
        return max_removed_edges

Big(O) Analysis

Time Complexity

O(2^(3*n)) – The brute force solution iterates through all possible combinations of edges to remove. If the input graph has '3*n' edges (where 'n' is the number of nodes, type 1 edges, type 2 edges and type 3 edges - each limited to at most n), there are 2^(3*n) possible subsets of edges to remove. For each subset, we need to check if the remaining graph is fully traversable, which takes O(n) time using depth-first search (DFS). Since we perform the traversability check for each of the 2^(3*n) subsets, the overall time complexity becomes O(2^(3*n) * n). However, 2^(3*n) dominates the time complexity, resulting in a final time complexity of O(2^(3*n)).

Space Complexity

O(2^E * (V + E)) – The algorithm explores all possible combinations of edges to remove. Generating all combinations of edges leads to storing up to 2^E combinations, where E is the number of edges. For each combination, a new graph is constructed, which requires space proportional to V + E, where V is the number of vertices and E is the number of edges. Therefore, the space complexity is O(2^E * (V + E)).

Optimal Solution

Approach

The problem asks to remove the maximum number of unnecessary connections from a network while still ensuring everyone can reach each other. The trick is to focus on the necessary connections first and identify the shared versus specific connections.

Here's how the algorithm would work step-by-step:

First, consider connections that only one person can use. These are absolutely necessary to include. Keep track of how many people can reach each other using only these connections.
Next, consider connections that both people can use. These connections are only added if adding them increases the number of people that can reach each other.
For the connections that both people can use, prioritize those connections that connect groups of people to make sure the number of people that can reach each other rises as fast as possible.
In the end, count the number of connections you used. Subtracting that from the total connections you originally had will give you the maximum number of connections you could remove.

Code Implementation

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

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

    def union(self, node_a, node_b):
        root_a = self.find(node_a)
        root_b = self.find(node_b)

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

def remove_max_number_of_edges(
    number_of_nodes, edges
):
    edges_needed = 0

    # DSU for person 1
    dsu_alice = DisjointSetUnion(number_of_nodes + 1)
    # DSU for person 2
    dsu_bob = DisjointSetUnion(number_of_nodes + 1)

    # First, handle type 3 edges - essential shared edges
    for edge_type, node_a, node_b in edges:
        if edge_type == 3:
            if dsu_alice.union(node_a, node_b):
                dsu_bob.union(node_a, node_b)
                edges_needed += 1

    # Then handle type 1 edges - edges only for person 1
    for edge_type, node_a, node_b in edges:
        if edge_type == 1:
            if dsu_alice.union(node_a, node_b):
                edges_needed += 1

    # Then handle type 2 edges - edges only for person 2
    for edge_type, node_a, node_b in edges:
        if edge_type == 2:
            if dsu_bob.union(node_a, node_b):
                edges_needed += 1

    # Finally handle type 3 edges
    # Check if there's still available unions using shared edges
    for edge_type, node_a, node_b in edges:
        if edge_type == 3:
            if dsu_alice.union(node_a, node_b):
                edges_needed += 1

    # Check connectivity for Alice
    number_of_components_alice = 0
    for node in range(1, number_of_nodes + 1):
        if dsu_alice.find(node) == node:
            number_of_components_alice += 1

    # Check connectivity for Bob
    number_of_components_bob = 0
    for node in range(1, number_of_nodes + 1):
        if dsu_bob.find(node) == node:
            number_of_components_bob += 1

    # We need to check if the graph is fully traversable
    if (
        number_of_components_alice > 1
        or number_of_components_bob > 1
    ):
        return -1

    # Calculate max edges that can be removed
    return len(edges) - edges_needed

Big(O) Analysis

Time Complexity

O(n + E * α(n)) – The algorithm iterates through all edges, which takes O(E) time, where E is the number of edges. Within the loop, a Union-Find data structure is used to determine connected components and merge them. The Union-Find operations (find and union) have a time complexity of α(n) on average, where α(n) is the inverse Ackermann function, which grows very slowly and is practically constant for any realistic input size. The initial setup of the Union-Find data structure takes O(n) time. Therefore, the overall time complexity is O(n + E * α(n)).

Space Complexity

O(N) – The algorithm uses a Disjoint Set Union (DSU) data structure, also known as Union-Find, implicitly within steps 1-3 to keep track of how many people can reach each other. This DSU typically involves an array of size N (where N is the number of people/nodes in the graph) to represent the parent of each node in the union-find structure. Therefore, the auxiliary space required for the DSU is proportional to the number of nodes, N. No other significant auxiliary data structures are used; thus, the overall space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input n or edges array	Return 0 if n is less than or equal to 1 and edges is null or empty, as no edges can be removed.
Graph is already fully traversable by both Alice and Bob with no edges removed	The algorithm should correctly identify this and return 0.
Graph is not fully traversable even after removing edges.	The algorithm should detect this and return -1.
Edges contain nodes outside the range [1, n]	Return -1 immediately, as the input is invalid.
Duplicate edges in the input	The DSU will treat these as single edges, so the algorithm will work correctly, possibly removing them unnecessarily, still obtaining an optimal solution.
All edges are of type 1 or type 2 (only Alice's or Bob's edges exist)	The algorithm must ensure both Alice and Bob can traverse the entire graph; return -1 if either cannot.
Input represents a disconnected graph with multiple components	The Disjoint Set Union (DSU) must connect all components for both Alice and Bob to ensure full traversal is possible.
Integer overflow possible during DSU operations with large n	Use appropriate data types (e.g., long) for parent array to avoid potential integer overflow during find/union operations.

Null or empty input n or edges array

How to Handle:

Return 0 if n is less than or equal to 1 and edges is null or empty, as no edges can be removed.

Graph is already fully traversable by both Alice and Bob with no edges removed

How to Handle:

The algorithm should correctly identify this and return 0.

Graph is not fully traversable even after removing edges.

How to Handle:

The algorithm should detect this and return -1.

Edges contain nodes outside the range [1, n]

How to Handle:

Return -1 immediately, as the input is invalid.

Duplicate edges in the input

How to Handle:

The DSU will treat these as single edges, so the algorithm will work correctly, possibly removing them unnecessarily, still obtaining an optimal solution.

All edges are of type 1 or type 2 (only Alice's or Bob's edges exist)

How to Handle:

The algorithm must ensure both Alice and Bob can traverse the entire graph; return -1 if either cannot.

Input represents a disconnected graph with multiple components

How to Handle:

The Disjoint Set Union (DSU) must connect all components for both Alice and Bob to ensure full traversal is possible.

Integer overflow possible during DSU operations with large n

How to Handle:

Use appropriate data types (e.g., long) for parent array to avoid potential integer overflow during find/union operations.