What is the time complexity of LeetCode 1579. Remove Max Number of Edges to Keep Graph Fully Traversable?

The Python solution on this page runs in O(V+E).

What is the space complexity of LeetCode 1579. Remove Max Number of Edges to Keep Graph Fully Traversable?

The Python solution on this page uses O(V) auxiliary space.

Remove Max Number of Edges to Keep Graph Fully Traversable — LeetCode 1579 Python Solution

HardUnion FindGraph

Problem: #1579
Pattern: Union-Find
Reading time: 7 min
Source: leetcode.com

The problem

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.

Example

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.

Python solution

Python

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

Complexity

Measure	Complexity
Time	O(V+E)
Space	O(V) auxiliary

Pattern: Union-Find

Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 1579. Remove Max Number of Edges to Keep Graph Fully Traversable is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.

The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1579. Remove Max Number of Edges to Keep Graph Fully Traversable?: LeetCode 1579. Remove Max Number of Edges to Keep Graph Fully Traversable is rated Hard on LeetCode.
What is the time complexity of LeetCode 1579. Remove Max Number of Edges to Keep Graph Fully Traversable?: The Python solution on this page runs in O(V+E).
What is the space complexity of LeetCode 1579. Remove Max Number of Edges to Keep Graph Fully Traversable?: The Python solution on this page uses O(V) auxiliary space.
What topics does LeetCode 1579. Remove Max Number of Edges to Keep Graph Fully Traversable cover?: LeetCode 1579. Remove Max Number of Edges to Keep Graph Fully Traversable is tagged Union Find and Graph on LeetCode.