1579. Remove Max Number of Edges to Keep Graph Fully Traversable

Problem Description

Alice and Bob have a special undirected graph that can only be traversed by them according to the types of edges it has. There are three types of edges in this graph:

Type 1 edges can only be traversed by Alice.
Type 2 edges can only be traversed by Bob.
Type 3 edges can be traversed by both Alice and Bob.

This graph is represented by an array of edges where each edge is expressed as [type_i, u_i, v_i]. Here, type_i indicates the type of the edge, while u_i and v_i are the nodes that this edge connects.

The objective is to determine the maximum number of edges that can be removed from the graph while still allowing Alice and Bob to traverse the entire graph. To "traverse the entire graph" means that Alice and Bob can reach all nodes from any starting node. If there's no way to traverse the entire graph by both Alice and Bob after the removal of any edges, the answer should be -1.

Intuition

The solution to the problem relies on the concept of 'union find' data structures which helps in keeping track of connected components in a graph. Initially, we consider all nodes as separate components. The objective is to connect these components step by step, minimizing the number of connections, which implies maximizing the removal of unnecessary edges.

To solve the problem, we create two separate union find instances—one for Alice and one for Bob. We start by looking at the Type 3 edges first because these edges are usable by both Alice and Bob. When we encounter a Type 3 edge, we attempt to merge the components in both Alice's and Bob's union find structures. If the components are already merged in both, it means that edge is not necessary for traversal, and it can be removed. After dealing with Type 3 edges, we individually process Type 1 and Type 2 edges for Alice and Bob, respectively.

The intuition here is that if we can't connect all nodes after processing all edges, then it's impossible for Alice or Bob to traverse the entire graph, in which case we return -1. However, if after processing all the edges Alice and Bob are each able to traverse the entire graph, we return the count of the number of edges we decided to remove.

Learn more about Union Find and Graph patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

O(1)O(log n)O(sqrt(n))O(n)

I don’t know

Solution Approach

The Reference Solution Approach mentions 'Union find', which is a key data structure used for this problem. Let's delve into how Union Find, also known as Disjoint Set Union (DSU), is used to solve this problem.

Union Find Data Structure

The Union Find data structure consists of two primary operations:

find operation determines which set a particular element belongs to. With path compression, it can perform nearly constant time complexity.
union operation merges two sets together if they are not already merged. Union by size ensures that the tree remains balanced, leading to faster union operations.

Union Find Class Implementation

We create a Union Find class, UnionFind, with the following characteristics:

An array p to store the parent of each node, initialized to each node being its own parent.
An array size which stores the sizes of the components represented by the roots, used to keep the tree balanced during union operation.
A cnt variable that keeps track of the count of separate components.

`find` Method

When the find method is called with a node x, it checks whether x is its own parent (leader of the component). If not, it recursively updates the parent of x to be the root of the component (path compression), thereby flattening the tree structure for future accesses.

`union` Method

The union method takes in two nodes a and b, finds their respective roots and if they belong to different components, joins the smaller component under the larger one (union by size). This not only helps in keeping the tree depth minimal but also reduces the time complexity of future find operations.

Algorithm

Initialize two instance of UnionFind, one for Alice and another for Bob, named ufa and ufb respectively.
Define a variable ans to count the number of edges that can be removed.

Processing Type 3 Edges

Iterate through the given edges. For edges of type 3:
- If union of the two connected nodes (u,v) is successful in ufa and ufb, no action is taken (the edge is needed).
- If union is not successful (already in the same component), increment ans because this edge can be removed.

Processing Type 1 and Type 2 Edges

Iterate through the given edges again.
- For edges of type 1, try to perform union in ufa. If the edge cannot help in further union (meaning that edge is redundant), increment ans.
- Similarly, for edges of type 2, perform union in ufb and if the edge is not needed, increment ans.

Conclusion

At the end, check if both Alice and Bob can traverse the whole graph; this is indicated by cnt being 1 for both ufa and ufb. If yes, return ans as the maximum number of edges that can be removed. Otherwise, return -1 indicating it’s not possible for Alice and Bob to traverse the entire graph after removing the edges.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

dp[i] = dp[i - 1] + dp[i - 2]dp[i] = dp[i - 1] + 1dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]dp[i] = dp[i - 1]

I don’t know

Example Walkthrough

Let's consider a simple example where the following edges are given for the graph:

1Edges = [[3, 1, 2], [3, 2, 3], [1, 1, 3], [2, 2, 4]]

Now, using the solution approach described above, we will determine the maximum number of edges that can be removed while ensuring both Alice and Bob can traverse the entire graph.

We initialize two instances of UnionFind, one for Alice (ufa) and one for Bob (ufb). Also, we define a variable ans and set it to 0, which will count the number of removable edges.
We start by considering the Type 3 edges. Here they are [[3, 1, 2], [3, 2, 3]].
- For the edge [3, 1, 2], we attempt to union node 1 and 2 in both ufa and ufb. Since they are separate components, they're merged, and ans remains 0.
- Next, for [3, 2, 3], we again attempt to union in both ufa and ufb. They are not in the same component, so we merge them, and ans remains 0.
Now, we process the Type 1 and Type 2 edges. Edges [1, 1, 3] and [2, 2, 4] are now considered.
- For the edge [1, 1, 3], we attempt to union node 1 and 3 in ufa. However, they are already connected through the Type 3 edge previously addressed, so this edge is not needed and ans is incremented to 1.
- For the edge [2, 2, 4], since node 4 is not connected to anything in ufb, it is combined with node 2, and ans stays at 1.
After processing all edges, we check if both ufa and ufb have covered all nodes. In this case, both have 3 nodes connected through edges, which means both Alice and Bob can traverse the entire graph.
Since Alice and Bob can traverse the entire graph, we return ans as the result. Therefore, the maximum number of edges that can be removed is 1 in this example. If it was not possible for both Alice and Bob to traverse the entire graph, we would have returned -1.

Solution Implementation

1class UnionFind:
2    def __init__(self, size):
3        # Initializes the UnionFind structure.
4        # Each node is its own parent at first, and the size of each set is 1.
5        # `count` tracks the number of disjoint sets.
6        self.parent = list(range(size))
7        self.set_size = [1] * size
8        self.count = size
9
10    def find(self, node):
11        # Recursively finds the root parent of a node.
12        # Applies path compression by linking the node directly to the root parent.
13        if self.parent[node] != node:
14            self.parent[node] = self.find(self.parent[node])
15        return self.parent[node]
16
17    def union(self, node1, node2):
18        # Merges the sets of node1 and node2.
19        # If they already share the same parent, no union is performed, returns False.
20        # Otherwise, the smaller set is merged into the larger one, and True is returned.
21        root1, root2 = self.find(node1 - 1), self.find(node2 - 1)
22        if root1 == root2:
23            return False
24        if self.set_size[root1] > self.set_size[root2]:
25            self.parent[root2] = root1
26            self.set_size[root1] += self.set_size[root2]
27        else:
28            self.parent[root1] = root2
29            self.set_size[root2] += self.set_size[root1]
30        self.count -= 1
31        return True
32
33
34class Solution:
35    def maxNumEdgesToRemove(self, num_nodes: int, edges: List[List[int]]) -> int:
36        # Initializes two UnionFind instances, one for Alice and one for Bob.
37        alice_union_find = UnionFind(num_nodes)
38        bob_union_find = UnionFind(num_nodes)
39        num_edges_removed = 0
40
41        # Adds type 3 edges (common to both Alice and Bob).
42        # If an edge cannot be added because it does not merge two different sets,
43        # it is considered redundant and can be removed.
44        for edge_type, node1, node2 in edges:
45            if edge_type == 3:
46                if not alice_union_find.union(node1, node2):
47                    num_edges_removed += 1
48                else:
49                    # Add the edge for Bob as well since it's a common edge.
50                    bob_union_find.union(node1, node2)
51
52        # Adds type 1 and type 2 edges (specific to Alice and Bob respectively).
53        # If an edge cannot be added because it does not merge two different sets,
54        # it is considered redundant and can be removed.
55        for edge_type, node1, node2 in edges:
56            if edge_type == 1:
57                # If the edge cannot be added, increment the removal count.
58                if not alice_union_find.union(node1, node2):
59                    num_edges_removed += 1
60            elif edge_type == 2:
61                if not bob_union_find.union(node1, node2):
62                    num_edges_removed += 1
63
64        # The graph is fully connected for both Alice and Bob only if both have exactly one set.
65        # In such a case, return the number of edges removed, otherwise return -1.
66        if alice_union_find.count == 1 and bob_union_find.count == 1:
67            return num_edges_removed
68        else:
69            return -1
70

1class UnionFind {
2    private int[] parent;    // Parent array to represent the disjoint set forest
3    private int[] size;      // Size array to count the number of elements in each set
4    public int count;        // Count of distinct sets
5
6    // Constructor initializes each node in its own set with size 1
7    public UnionFind(int n) {
8        parent = new int[n];
9        size = new int[n];
10        for (int i = 0; i < n; ++i) {
11            parent[i] = i;
12            size[i] = 1;
13        }
14        count = n;
15    }
16
17    // Find the root of the set in which element x is present
18    // Uses path compression for efficiency
19    public int find(int x) {
20        if (parent[x] != x) {
21            parent[x] = find(parent[x]);  // path compression
22        }
23        return parent[x];
24    }
25
26    // Union function to merge sets containing elements 'a' and 'b'
27    // Returns true if a merge happened, false if already in the same set
28    public boolean union(int a, int b) {
29        int rootA = find(a - 1), rootB = find(b - 1);
30        if (rootA == rootB) {
31            return false;  // Already in the same set
32        }
33        if (size[rootA] > size[rootB]) {  // Merge smaller set into larger set
34            parent[rootB] = rootA;
35            size[rootA] += size[rootB];
36        } else {
37            parent[rootA] = rootB;
38            size[rootB] += size[rootA];
39        }
40        --count;  // Decrease the number of sets
41        return true;
42    }
43}
44
45class Solution {
46    // Function to find the maximum number of edges that can be removed from the input graph
47    // Returns -1 if Alice and Bob cannot both traverse the entire graph
48    public int maxNumEdgesToRemove(int n, int[][] edges) {
49        UnionFind aliceSet = new UnionFind(n);
50        UnionFind bobSet = new UnionFind(n);
51        int numEdgesToRemove = 0;  // Tracks the number of edges we can remove
52
53        // First, process type 3 edges which are shared by Alice and Bob
54        for (int[] edge : edges) {
55            int type = edge[0], u = edge[1], v = edge[2];
56            if (type == 3) {
57                // Union operations for shared edges. If union operation fails
58                // (i.e., edge is redundant), increment numEdgesToRemove.
59                if (!aliceSet.union(u, v)) {
60                    numEdgesToRemove++;
61                } else {
62                    bobSet.union(u, v);  // We can safely ignore return val since aliceSet succeeded
63                }
64            }
65        }
66
67        // Process Alice-only and Bob-only edges
68        for (int[] edge : edges) {
69            int type = edge[0], u = edge[1], v = edge[2];
70            if (type == 1 && !aliceSet.union(u, v)) {  // Alice-only edge
71                numEdgesToRemove++;  // If edge is already connected then increment the removal count
72            }
73            if (type == 2 && !bobSet.union(u, v)) {  // Bob-only edge
74                numEdgesToRemove++;  // If edge is already connected then increment the removal count
75            }
76        }
77
78        // If both Alice's and Bob's sets are fully connected (i.e., count is 1 for both),
79        // return number of edges removed. Otherwise, return -1 since they cannot
80        // both traverse the entire graph.
81        return (aliceSet.count == 1 && bobSet.count == 1) ? numEdgesToRemove : -1;
82    }
83}
84

1#include <vector>
2#include <numeric>
3using namespace std;
4
5// Union-Find Disjoint Set implementation
6class UnionFind {
7public:
8    vector<int> parents; // Store the parent of each element
9    vector<int> sizes; // Store the size of each set
10    int count; // Counter for the number of disjoint sets
11
12    // Constructor to initialize Union-Find structure with `n` elements
13    UnionFind(int n): count(n), parents(n), sizes(n, 1) {
14        // Initialize parents to themselves and
15        // sizes to 1 for each element
16        iota(parents.begin(), parents.end(), 0);
17    }
18
19    // Function to merge the sets containing elements `a` and `b`
20    bool unite(int a, int b) {
21        int parentA = find(a - 1);
22        int parentB = find(b - 1);
23        if (parentA == parentB) {
24            // `a` and `b` are already in the same set
25            return false;
26        }
27        if (sizes[parentA] > sizes[parentB]) {
28            // Merge the smaller set into the larger set
29            parents[parentB] = parentA;
30            sizes[parentA] += sizes[parentB];
31        } else {
32            // Merge the smaller or equal size set into the other
33            parents[parentA] = parentB;
34            sizes[parentB] += sizes[parentA];
35        }
36        --count; // Reduce the count of disjoint sets
37        return true;
38    }
39
40    // Function to find the root parent of element `x`
41    int find(int x) {
42        if (parents[x] != x) {
43            // Path compression step to flatten tree
44            parents[x] = find(parents[x]);
45        }
46        return parents[x];
47    }
48};
49
50// Solution class for the specific problem
51class Solution {
52public:
53    // Function to find the maximum number of edges that can be removed
54    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
55        UnionFind ufa(n); // Union-Find for Alice
56        UnionFind ufb(n); // Union-Find for Bob
57        int removalCount = 0; // Counter for the number of edges removed
58
59        // First, we deal with type 3 edges, which benefit both Alice and Bob
60        for (auto& edge : edges) {
61            if (edge[0] == 3) {
62                bool united = ufa.unite(edge[1], edge[2]);
63                ufb.unite(edge[1], edge[2]); // Note: `unite` results should be the same for ufa and ufb
64                if (!united) {
65                    // Edge not necessary, count it for removal
66                    ++removalCount;
67                }
68            }
69        }
70
71        // Next, process type 1 and type 2 edges separately for Alice and Bob
72        for (auto& edge : edges) {
73            int type = edge[0], u = edge[1], v = edge[2];
74            if (type == 1) {
75                // Type 1 edges for Alice; increase removal count if not united
76                removalCount += !ufa.unite(u, v);
77            }
78            if (type == 2) {
79                // Type 2 edges for Bob; increase removal count if not united
80                removalCount += !ufb.unite(u, v);
81            }
82        }
83
84        // Check if both Alice and Bob have connected graphs
85        if (ufa.count == 1 && ufb.count == 1) {
86            // All vertices are connected for both, so return the removal count
87            return removalCount;
88        } else {
89            // Not all vertices are connected (one or both are disconnected)
90            return -1;
91        }
92    }
93};
94

1type UnionFind = {
2    parents: number[];
3    sizes: number[];
4    count: number;
5};
6
7// Initialize Union-Find structure with `n` elements
8function createUnionFind(n: number): UnionFind {
9    const parents = Array.from({ length: n }, (_, index) => index);
10    const sizes = new Array(n).fill(1);
11    return { parents, sizes, count: n };
12}
13
14// Find the root parent of element `x`
15function find(unionFind: UnionFind, x: number): number {
16    if (unionFind.parents[x] !== x) {
17        // Path compression step to flatten the hierarchy
18        unionFind.parents[x] = find(unionFind, unionFind.parents[x]);
19    }
20    return unionFind.parents[x];
21}
22
23// Merge the sets containing elements `a` and `b`
24function unite(unionFind: UnionFind, a: number, b: number): boolean {
25    let parentA = find(unionFind, a - 1);
26    let parentB = find(unionFind, b - 1);
27    if (parentA === parentB) {
28        // `a` and `b` are already in the same set
29        return false;
30    }
31    if (unionFind.sizes[parentA] > unionFind.sizes[parentB]) {
32        // Merge the smaller set into the larger set
33        unionFind.parents[parentB] = parentA;
34        unionFind.sizes[parentA] += unionFind.sizes[parentB];
35    } else {
36        // Merge the smaller or equal size set into the other one
37        unionFind.parents[parentA] = parentB;
38        unionFind.sizes[parentB] += unionFind.sizes[parentA];
39    }
40    unionFind.count--; // Reduce the count of disjoint sets
41    return true;
42}
43
44// Function to find the maximum number of edges that can be removed
45function maxNumEdgesToRemove(n: number, edges: number[][]): number {
46    let ufa = createUnionFind(n); // Union-Find for Alice
47    let ufb = createUnionFind(n); // Union-Find for Bob
48    let removalCount = 0; // Counter for the number of edges removed
49
50    // First, handle type 3 edges, which benefit both Alice and Bob
51    for (let edge of edges) {
52        if (edge[0] === 3) {
53            let unitedA = unite(ufa, edge[1], edge[2]);
54            unite(ufb, edge[1], edge[2]); // Should have the same result for ufb
55            if (!unitedA) {
56                // Edge is not necessary; increment removal count
57                removalCount++;
58            }
59        }
60    }
61
62    // Next, process type 1 and type 2 edges separately for Alice and Bob
63    for (let edge of edges) {
64        let type = edge[0], u = edge[1], v = edge[2];
65        if (type === 1) {
66            // Type 1 edges for Alice; increase removal count if not united
67            removalCount += !unite(ufa, u, v) ? 1 : 0;
68        } else if (type === 2) {
69            // Type 2 edges for Bob; increase removal count if not united
70            removalCount += !unite(ufb, u, v) ? 1 : 0;
71        }
72    }
73
74    // Check if both Alice and Bob have connected graphs
75    if (ufa.count === 1 && ufb.count === 1) {
76        // All vertices are connected for both, so return the removal count
77        return removalCount;
78    } else {
79        // Not all vertices are connected (one or both are disconnected)
80        return -1;
81    }
82}
83

Not Sure What to Study? Take the 2-min Quiz：

Which of the following is a good use case for backtracking?

Combinatorial problemsRandom number generationTopological sortingMatrix multiplication

I don’t know

Time and Space Complexity

Time Complexity

The main time-consuming operations in this code are the two for loops that iterate over the edges and the find and union operations of the UnionFind data structure.

Initializing the UnionFind structure with n elements takes O(n) time as it initializes two lists of length n.
The find operation uses path compression which, in the amortized case, yields a time complexity close to constant time O(1). However, without amortization and in the worst case without path compression, it could take O(n).
The union operation also has an amortized time complexity of O(1) since it potentially involves two find operations and simple assignment and arithmetic operations.
The first for loop iterates over all edges. If there are E edges of type 3, in the worst case, where the union operation might include traversing the height of the trees, this loop runs in O(E) time. Due to path compression and the balancing by size, this is typically much faster on average, but strictly speaking and not accounting for amortization, it's O(E * alpha(n)), where alpha(n) is the Inverse Ackermann function, which grows extremely slowly and is practically constant.
The second for loop is similar to the first one, it goes through all edges again and attempts to union them. This results in the same time complexity analysis as above.

Therefore, assuming E is the total number of edges, the total time complexity of the Solution.maxNumEdgesToRemove is O(E * alpha(n)), noting that for all practical purposes, alpha(n) can be considered a constant and thus the time complexity is effectively O(E).

Space Complexity

The space complexity is mainly due to the UnionFind data structure which holds two arrays p and size of length n and the inputs themselves.

The UnionFind structure uses O(n) space because of the parent array and the size array, both of which have n elements.
There is no additional space used that grows with the input size, except for the input edges themselves, which is external and not part of the space complexity of this algorithm.

Therefore, the total space complexity of the Solution.maxNumEdgesToRemove is O(n) where n is the number of vertices.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10][100, 33, 30][10, 12, 20]

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1579. Remove Max Number of Edges to Keep Graph Fully Traversable

Problem Description

Intuition

Solution Approach

Union Find Data Structure

Union Find Class Implementation

find Method

union Method

Algorithm

Processing Type 3 Edges

Processing Type 1 and Type 2 Edges

`find` Method

`union` Method