Untitled

mail@pastecode.io avatar
unknown
python
7 months ago
845 B
2
Indexable
Never
class Solution:
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        parent = [i for i in range(n)]
        rank = [1 for i in range(n)]
        totalRank = 0

        def find(n):
            while n != parent[n]:
                parent[n] = parent[parent[n]]
                n = parent[n]
            return n
        
        def union(n1, n2):
            nonlocal totalRank
            p1, p2 = find(n1), find(n2)

            if p1 == p2:
                return

            totalRank += 1
            if rank[p1] > rank[p2]:
                parent[p2] = p1
                rank[p1] += rank[p2]
            else:
                parent[p1] = p2
                rank[p2] += rank[p1]
            
            return
        
        for s, e in roads:
            union(s, e)
        
        return totalRank + 1