#1579

Hard

LeetCode Problem Workspace

Remove Max Number of Edges to Keep Graph Fully Traversable

Maximize the number of edges that can be removed while keeping the graph fully traversable for both Alice and Bob.

Problem Statement

You are given an undirected graph with n nodes and three types of edges: type 1, type 2, and type 3. Each edge is represented by an array [typei, ui, vi], where typei is the edge type and ui and vi are the connected nodes. The task is to find the maximum number of edges you can remove from the graph while ensuring that Alice and Bob can still fully traverse the graph, meaning they can reach all other nodes starting from any node.

You must return the maximum number of edges that can be removed, or return -1 if it is not possible for both Alice and Bob to fully traverse the graph. Note that both Alice and Bob must be able to reach all nodes independently of each other. The edges represent different types of actions that can be removed to optimize the graph's structure.

Examples

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

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

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

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 <= 105
1 <= edges.length <= min(105, 3 * n * (n - 1) / 2)
edges[i].length == 3
1 <= typei <= 3
1 <= ui < vi <= n
All tuples (typei, ui, vi) are distinct.

Solution Approach

Union Find Data Structure

The Union Find (or Disjoint Set Union) data structure is ideal for solving this problem. It helps efficiently manage and track connected components of nodes. By performing union operations on the nodes connected by edges, we can determine which edges are necessary to maintain full traversal for both Alice and Bob.

Edge Type Prioritization

Start by prioritizing type 3 edges, as they benefit both Alice and Bob simultaneously. Next, handle type 1 edges for Alice and type 2 edges for Bob. This prioritization ensures that we remove as many edges as possible while still preserving full traversal capabilities for both individuals.

Maximizing Removals

Once all necessary edges are kept to maintain traversal, the remaining edges are the ones that can be removed. The goal is to maximize the number of edges removed without disconnecting the graph for either Alice or Bob. This involves analyzing the connectivity and determining which edges are redundant.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this problem is largely determined by the Union Find operations, which are nearly constant time due to the use of path compression and union by rank. The space complexity depends on the number of nodes and edges, specifically the storage of the parent, rank, and component arrays, which scale with O(n + m) where m is the number of edges.

What Interviewers Usually Probe

Familiarity with Union Find techniques and optimizations.
Understanding of graph traversal and edge prioritization.
Ability to handle large inputs efficiently using path compression and union by rank.

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle all types of edges properly, leading to unnecessary removals.
Not correctly applying Union Find operations, leading to incorrect traversal determination.
Overlooking edge prioritization, which can result in suboptimal edge removal.

Follow-up variants

Implement the solution with DFS or BFS to explore graph connectivity before removing edges.
Handle more edge types with different traversal requirements.
Optimize the solution for higher input limits by improving the Union Find structure.

FAQ

How can Union Find help solve the 'Remove Max Number of Edges to Keep Graph Fully Traversable' problem?

Union Find is essential for tracking connectivity between nodes. It allows us to efficiently check if adding or removing an edge maintains full traversal for both Alice and Bob.

What is the role of edge types in this problem?

Edge types are important for determining which edges to prioritize for removal. Type 3 edges benefit both Alice and Bob, while type 1 and type 2 edges benefit only one of them.

What happens if Alice and Bob can't fully traverse the graph?

If either Alice or Bob can't reach all nodes, the answer is -1, indicating that it's impossible to maintain full traversal after edge removals.

Why is the Union Find data structure preferred for this problem?

Union Find is efficient for tracking connected components in large graphs. It allows for fast merging of nodes and checking of graph connectivity, which is crucial for this problem's solution.

Can this problem be solved without Union Find?

While it's possible to use DFS or BFS for connectivity, Union Find offers a more efficient solution for this problem, particularly for large graphs with many edges.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

class UnionFind:
    def __init__(self, n):
        self.p = list(range(n))
        self.size = [1] * n
        self.cnt = n

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

    def union(self, a, b):
        pa, pb = self.find(a - 1), self.find(b - 1)
        if pa == pb:
            return False
        if self.size[pa] > self.size[pb]:
            self.p[pb] = pa
            self.size[pa] += self.size[pb]
        else:
            self.p[pa] = pb
            self.size[pb] += self.size[pa]
        self.cnt -= 1
        return True


class Solution:
    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
        ufa = UnionFind(n)
        ufb = UnionFind(n)
        ans = 0
        for t, u, v in edges:
            if t == 3:
                if ufa.union(u, v):
                    ufb.union(u, v)
                else:
                    ans += 1
        for t, u, v in edges:
            if t == 1:
                ans += not ufa.union(u, v)
            if t == 2:
                ans += not ufb.union(u, v)
        return ans if ufa.cnt == 1 and ufb.cnt == 1 else -1

Continue Practicing

#1584 min cost to connect all points #1632 rank transform of a matrix #1489 find critical and pseudo critical edges in minimum spanning tree