Untitled

 avatar
unknown
plain_text
2 years ago
1.7 kB
10
Indexable
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [1] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False

        if self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        elif self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        return True

def minOperations(comp_nodes, comp_from, comp_to):
    if len(comp_from) != len(comp_to):
        return -1

    n = comp_nodes
    uf = UnionFind(n)

    # Check if all nodes in comp_from and comp_to are within the valid range
    for i in range(len(comp_from)):
        if comp_from[i] < 1 or comp_from[i] > n or comp_to[i] < 1 or comp_to[i] > n:
            return -1

    # Connect initial groups and keep track of the number of groups
    groups_count = n
    for i in range(len(comp_from)):
        if uf.union(comp_from[i] - 1, comp_to[i] - 1):
            groups_count -= 1

    # If all computers are in the same group, no operation is needed
    if groups_count == 1:
        return 0

    # The minimum number of operations needed is equal to the number of groups - 1
    return groups_count - 1

# Test example
comp_nodes = 4
comp_from = [1,2]
comp_to = [3,4]
print(minOperations(comp_nodes, comp_from, comp_to))  # Output: 1
Editor is loading...