Untitled
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...