Facebook
From josema, 1 Month ago, written in Python.
Embed
Download Paste or View Raw
Hits: 128
  1. class UnionFind:
  2.     def __init__(self, size):
  3.         self.parent = list(range(size))
  4.         self.rank = [0] * size
  5.    
  6.     def find(self, u):
  7.         if self.parent[u] != u:
  8.             self.parent[u] = self.find(self.parent[u])
  9.         return self.parent[u]
  10.    
  11.     def union(self, u, v):
  12.         root_u = self.find(u)
  13.         root_v = self.find(v)
  14.         if root_u != root_v:
  15.             if self.rank[root_u] > self.rank[root_v]:
  16.                 self.parent[root_v] = root_u
  17.             elif self.rank[root_u] < self.rank[root_v]:
  18.                 self.parent[root_u] = root_v
  19.             else:
  20.                 self.parent[root_v] = root_u
  21.                 self.rank[root_u] += 1
  22.  
  23. def find_visible_profiles(n, m, from_list, to_list, queries):
  24.     uf = UnionFind(n + 1)
  25.     for u, v in zip(from_list, to_list):
  26.         uf.union(u, v)
  27.    
  28.      comp * (n + 1)
  29.     for node in range(1, n + 1):
  30.         root = uf.find(node)
  31.         component_size[root] += 1
  32.    
  33.     return [component_size[uf.find(query)] for query in queries]