1319.-number-of-operations-to-make-network-connected.md

1319. Number of Operations to Make Network Connected

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        ans = -1
        if n - 1 > len(connections):
            return ans

        f = [i for i in range(n)]
        size = [1 for i in range(n)]

        def find(x):
            if f[x] != x:
                f[x] = find(f[x])

            return f[x]

        def union(x, y):
            fx = find(x)
            fy = find(y)
            if fx != fy:
                if size[fx] < size[fx]:
                    size[fx] += size[fy]
                    f[fy] = fx 
                else:
                    size[fy] += size[fx]
                    f[fx] = fy 
                return True

            return False

        value = 0
        for x, y in connections:
            if not union(x, y):
                value += 1
        need = sum(1 for i in range(n) if find(i) == i) - 1
        # print(value, need)
        if need > value:return ans
        return need