Skip to content

Graph Others

Table of Contents

1042. Flower Planting With No Adjacent

1761. Minimum Degree of a Connected Trio in a Graph

2508. Add Edges to Make Degrees of All Nodes Even

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

  • LeetCode | LeetCode CH (Hard)

  • Tags: union find, graph

  • Return the maximum number of edges you can remove so that the graph remains fully traversable.

1579

1579. Remove Max Number of Edges to Keep Graph Fully Traversable - Python Solution
from typing import List


# Kruskal
def maxNumEdgesToRemove(n: int, edges: List[List[int]]) -> int:
    alice, bob = UnionFind(n), UnionFind(n)
    visited = 0

    for t, u, v in edges:
        if t == 3:
            if alice.union(u, v) | bob.union(u, v):
                visited += 1

    for t, u, v in edges:
        if t == 1:
            if alice.union(u, v):
                visited += 1
        elif t == 2:
            if bob.union(u, v):
                visited += 1

    if alice.components > 1 or bob.components > 1:
        return -1

    return len(edges) - visited


class UnionFind:
    def __init__(self, n):
        self.parent = {i: i for i in range(1, n + 1)}
        self.rank = {i: 0 for i in range(1, n + 1)}
        self.components = n

    def find(self, n):
        p = self.parent[n]
        while self.parent[p] != p:
            self.parent[p] = self.parent[self.parent[p]]
            p = self.parent[p]
        return p

    def union(self, n1, n2):
        p1, p2 = self.find(n1), self.find(n2)

        if p1 == p2:
            return False

        if self.rank[p1] > self.rank[p2]:
            self.parent[p2] = p1
        elif self.rank[p1] < self.rank[p2]:
            self.parent[p1] = p2
        else:
            self.parent[p2] = p1
            self.rank[p1] += 1

        self.components -= 1

        return True


n = 4
edges = [[3, 1, 2], [3, 2, 3], [1, 1, 3], [1, 2, 4], [1, 1, 2], [2, 3, 4]]
print(maxNumEdgesToRemove(n, edges))  # 2

2065. Maximum Path Quality of a Graph

1697. Checking Existence of Edge Length Limited Paths

2242. Maximum Score of a Node Sequence

2493. Divide Nodes Into the Maximum Number of Groups

  • LeetCode | LeetCode CH (Hard)

  • Tags: depth first search, breadth first search, union find, graph

1782. Count Pairs Of Nodes

3435. Frequencies of Shortest Supersequences

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, string, bit manipulation, graph, topological sort, enumeration

277. Find the Celebrity

1724. Checking Existence of Edge Length Limited Paths II

2077. Paths in Maze That Lead to Same Room

Comments