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

Problem Explanation

The aim of this problem is to find the maximum number of edges from a graph that you can remove, while still ensuring the remaining graph can be fully traversed by Alice and Bob. This means that starting from any node, they can reach all other nodes.

The graph is made up of n nodes and 3 types of edges between the nodes:

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

The graph is represented by an array edges where each sub-array, edges[i] is a three-element array [typei, ui, vi]. This sub-array represents a bidirectional edge of type typei between nodes ui and vi.

Given this graph, the challenge is to determine how many edges can be removed while keeping the graph traversable for both Alice and Bob.

If the graph cannot be fully traversed by both after removing some edges, we should return -1.

Approach of the Solution

A union-find data structure is used to solve this problem efficiently.

The implemented class UnionFind is a data structure which keeps track of a partition of a set into disjoint (non-overlapping) subsets.

A few points about the Union-Find data structure:

• It has a notion of a 'parent' with each subset having one 'parent'.
• Initially all elements are in their own set.
• The 'union' operation merges together two sets.

In this problem, we create two instances of the UnionFind class, one for Alice and one for Bob representing the disjoint sets of nodes that each can traverse.

We then sort the edges list in descending order so that edges that can be traversed by both Alice and Bob (type 3 edges) are at the front. Our aim is to keep as many type 3 edges as possible.

We then iterate through the sorted list of edges and try to add each edge to Alice's and Bob's disjoint sets (for type 3 edges) or to the correct individual set (for type 1 or type 2 edges). We increment requiredEdges variable each time we succeed in adding an edge to a set.

If at the end, Alice and Bob both have one set each (indicating they can each traverse the graph), we return the difference between total edges and required edges (which will be the number of edges that can be removed). If Alice or Bob has multiple disjoint sets, we return -1 as it would be impossible to create a traversable graph for either Alice or Bob.

Example

Let's consider an example where n = 4 and edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]].

After sorting the edges, we get [[3,1,2],[3,2,3],[2,3,4],[1,1,3],[1,2,4],[1,1,2]].

We now start adding the edges to Alice's and Bob's sets.

For the first edge, [3,1,2], Alice and Bob can both traverse this edge, so we add it to both their sets and increment requiredEdges by 1.

Similarly, we add the second edge [3,2,3] to both sets, and then the type 2 and type 1 edges to their respective sets.

In the end, Alice and Bob both have one single joined set each. Since the count of required edges is 4, we return the number of edges we can remove, which is 6 - 4 = 2.

Solutions

Python

1
2python
3class UnionFind:
4    def __init__(self, n):
5        self.parent = list(range(n))
6        self.size = [1] * n
7        self.n = n
8
9    def find(self, x):
10        if self.parent[x] != x:
11            self.parent[x] = self.find(self.parent[x])
12        return self.parent[x]
13
14    def union(self, x, y):
15        px, py = self.find(x), self.find(y)
16        if px == py:
17            return False
18
19        if self.size[px] > self.size[py]:
20            px, py = py, px
21        self.parent[px] = py
22        self.size[py] += self.size[px]
23        self.n -= 1
24        return True
25
26class Solution:
27    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
28        alice, bob = UnionFind(n), UnionFind(n)
29        for idx, _, u, v in sorted((t, idx, u - 1, v - 1) for idx, (t, u, v) in enumerate(edges)):
30            if idx >= (10**5):
31                break
32            edges[idx] = (alice.union(u, v) or bob.union(u, v))
33
34        if any(t == 1 and not alice.union(u, v) or t == 2 and not bob.union(u, v)
35               for idx, (t, u, v) in enumerate(edges) if idx < (10**5)):
36            return -1
37        return len(edges) - alice.n - bob.n

Java

1
2java
3class Solution {
4    public int maxNumEdgesToRemove(int n, int[][] edges) {
5        UnionFind unionFindAlice = new UnionFind(n), unionFindBob = new UnionFind(n);
6        int removedEdges = 0;
7        for (int[] edge : edges) {
8            if (edge[0] == 3) {
9                if (!unionFindAlice.union(edge[1], edge[2])) {
10                    removedEdges++;
11                } else {
12                    unionFindBob.union(edge[1], edge[2]);
13                }
14            }
15        }
16        for (int[] edge : edges) {
17            if (edge[0] == 1) {
18                if (!unionFindAlice.union(edge[1], edge[2])) removedEdges++;
19            } else if (edge[0] == 2) {
20                if (!unionFindBob.union(edge[1], edge[2])) removedEdges++;
21            }
22        }
23        if (unionFindAlice.getCount() > 1 || unionFindBob.getCount() > 1) return -1;
24        return removedEdges;
25    }
26
27    class UnionFind {
28        private int count;
29        private int[] parent;
30        private int[] rank;
31
32        public UnionFind(int n) {
33            this.count = n;
34            this.parent = new int[n + 1];
35            this.rank = new int[n + 1];
36            for (int i = 0; i <= n; i++) {
37                parent[i] = i;
38                rank[i] = 1;
39            }
40        }
41
42        public int getCount() {
43            return count;
44        }
45
46        public int find(int x) {
47            while (x != parent[x]) {
48                parent[x] = parent[parent[x]];
49                x = parent[x];
50            }
51            return x;
52        }
53
54        public boolean union(int x, int y) {
55            int rootX = find(x), rootY = find(y);
56            if (rootX == rootY) return false;
57
58            if (rank[rootX] < rank[rootY]) {
59                parent[rootX] = rootY;
60                rank[rootY] += rank[rootX];
61            } else if (rank[rootY] < rank[rootX]) {
62                parent[rootY] = rootX;
63                rank[rootX] += rank[rootY];
64            } else {
65                parent[rootY] = rootX;
66                rank[rootX] += rank[rootY];
67            }
68            count--;
69            return true;
70        }
71    }
72}

Javascript

1
2javascript
3class UnionFind {
4    constructor(n) {
5        this.parent = new Array(n).fill(0).map((ele, idx) => idx);
6    }
7
8    find(a) {
9        let tmp = a;
10        while (tmp !== this.parent[tmp]) {
11            tmp = this.parent[tmp];
12        }
13        while (a !== tmp) {
14            let j = this.parent[a];
15            this.parent[a] = tmp;
16            a = j;
17        }
18        return tmp;
19    }
20    
21    union(a, b) {
22        let rootA = this.find(a);
23        let rootB = this.find(b);
24        if (rootA === rootB) return false;
25        this.parent[rootA] = rootB;
26        return true;
27    }
28}
29
30var maxNumEdgesToRemove = function(n, edges) {
31    let alice = new UnionFind(n);
32    let bob = new UnionFind(n);
33    let left = edges.length;
34    
35    for (let [type, u, v] of edges) {
36        if (type !== 3) continue;
37        u--; v--;
38        if (alice.union(u, v) || bob.union(u, v)) left--;
39    }
40    
41    for (let [type, u, v] of edges) {
42        if (type === 3) continue;
43        u--; v--;
44        if (type === 1 && alice.union(u, v)) left--;
45        if (type === 2 && bob.union(u, v)) left--;
46    }
47    
48    for (let i = 1; i < n; i++) {
49        if (alice.find(0) !== alice.find(i) || bob.find(0) !== bob.find(i)) return -1;
50    }
51    
52    return left;
53};

C++

1
2cpp
3class dsu {
4private:
5    vector<int> parent, rank;
6public:
7    dsu(int n) : parent(n), rank(n, 0) {
8        for (int i = 0; i < n; i++)
9            parent[i] = i;
10    }
11    int find(int u) {
12        if (u != parent[u])
13            parent[u] = find(parent[u]);
14        return parent[u];
15    }
16    bool Union(int u, int v) {
17        int x = find(u), y = find(v);
18        if (x == y) 
19            return false;
20        if (rank[x] < rank[y])
21            parent[x] = y;
22        else if (rank[x] > rank[y])
23            parent[y] = x;
24        else {
25            parent[y] = x;
26            rank[x]++;
27        }
28        return true;
29    }
30};
31    class Solution {
32public:
33    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
34        dsu dsu1(n), dsu2(n);
35        int ans = 0;
36        for (auto &edge : edges)
37            if (edge[0] == 3) {
38                edge[0] = dsu1.Union(edge[1]-1, edge[2]-1) ? 1 : 2;
39                if (edge[0] == 1) 
40                    dsu2.Union(edge[1]-1, edge[2]-1);
41                else 
42                    ans++;
43            }
44        for (auto &edge : edges)
45            if (!dsu1.Union(edge[1]-1, edge[2]-1) || !dsu2.Union(edge[1]-1, edge[2]-1))
46                ans++;
47            return dsu1.find(0) != dsu1.find(n-1) || dsu2.find(0) != dsu2.find(n-1) ? -1 : ans;
48    }
49};

C#

1
2csharp
3public class UnionFind {
4    private int[] parent;
5    private int[] rank;
6    private int count;
7    public UnionFind(int size) {
8        parent = new int[size];
9        rank = new int[size];
10        for (var i = 0; i < size; ++i) {
11            parent[i] = i;
12            rank[i] = 0;
13        }
14        count = size;
15    }
16    public int Find(int p) {
17        while (p != parent[p]) {
18            parent[p] = parent[parent[p]];
19            p = parent[p];
20        }
21        return p;
22    }
23    public bool Union(int p, int q) {
24        var rootP = Find(p);
25        var rootQ = Find(q);
26        if (rootP == rootQ)
27            return false;
28        if (rank[rootP] < rank[rootQ]) {
29            parent[rootP] = rootQ;
30        }
31        else {
32            parent[rootQ] = rootP;
33            if (rank[rootP] == rank[rootQ]) {
34                rank[rootP]++;
35            }
36        }
37        count--;
38        return true;
39    }
40    public int GetCount() {
41        return count;
42    }
43}
44public class Solution {
45    public int MaxNumEdgesToRemove(int n, int[][] edges) {
46        var alice = new UnionFind(n);
47        var bob = new UnionFind(n);
48        var count = 0;
49        edges = edges.OrderBy(edge => -edge[0]).ToArray();
50        foreach (var edge in edges) {
51            edge[1]--;
52            edge[2]--;
53            if (edge[0] <= 2 && bob.Union(edge[1], edge[2]) 
54                || edge[0] % 2 == 1 && alice.Union(edge[1], edge[2])) {
55                count++;
56                continue;
57            }
58            if (bob.Union(edge[1], edge[2])) {
59                alice.Union(edge[1], edge[2]);
60            }
61            else {
62                count--;
63            }
64        }
65        if (alice.GetCount() > 1 || bob.GetCount() > 1) {
66            return -1;
67        }
68        return edges.Length - count;
69    }
70}

In the solution:

• A helper class UnionFind is defined, which is used to manage the structure of Alice's and Bob's graph as they traverse.
• The helper's functions find and union are used to perform Union-Find operations, to detect and link disjoint subsets of nodes.
• In the main function, two UnionFind instances, alice and bob are created. They represent the state of the graph for Alice and Bob respectively, throughout edge addition.
• The list of edges sorted by edge type so that edges that can be traversed by both Alice and Bob (type 3 edges) are at the front.
• The function then iterates through the list of edges and tries to add each edge to Alice and Bob's UnionFind instance, depending on the edge type.
• If an edge is added successfully, the counter requiredEdges is incremented. If not, it means that the edge isn't connecting two previously unconnected nodes and can be removed.
• Finally, if Alice and Bob both have one set each (which means that every node in the graph can be reached by each of them), we return the number of edges that can be removed. If Alice or Bob has more than one set (which means there are nodes that are unreachable), we return -1.These solutions implement the Union-Find data structure, which can be used to efficiently handle the operations of finding the parent of a certain element and merging two sets.

This ability is especially beneficial in this problem since it allows us to dynamically monitor the connectivity of a graph, by enabling us to add and remove edges between nodes, while always knowing whether the graph is connected or not.

It's also worth noting that the Python, Javascript, C# and C++ solutions all follow a similar logic and approach. Each one supports their respective language's syntax, but essentially, they represent the same solution strategy.

As for Java solution, it takes a bit different approach. It sorts the edges by type to only add type 3 edges once, and then iterates over edges again to add type 1 and type 2 edges. The end result is the same, but with slightly different execution steps.

Overall, the function provides an effective solution to find out the maximum number of edges that can be removed from the graph, while still ensuring that it remains fully traversable by Alice and Bob. By leveraging the power of Union-Find data structure, this function manages to solve the problem in an efficient and elegant way.

In terms of time complexity, both Python and Java solutions sort the edges first which takes O(m log m) time where m is the number of edges. Then, Union-Find operations for each edge are performed which in worst case would take O(m) time. Therefore, the overall time complexity would be O(m log m + m) which simplifies to O(m log m). The space complexity is O(n + m) where n is the number of nodes, since we maintain Union-Find data structures for Alice and Bob each having n elements and an array to store the edges of length m.

These solutions should render fine for large inputs due to the efficiency of the Union-Find data structure. However, if you encounter performance problems, consider using a more efficient data structure or optimizing the Union-Find operations to improve the efficiency.