Facebook
From josema, 1 Month ago, written in Python.
Embed
Download Paste or View Raw
Hits: 119
  1. class UnionFind:
  2.     def __init__(self, size):
  3.         self.parent = list(range(size))
  4.         self.rank = [1] * size
  5.    
  6.     def find(self, u):
  7.         if self.parent[u] != u:
  8.             self.parent[u] = self.find(self.parent[u])  # Path compression
  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.        
  15.         if root_u != root_v:
  16.             # Union by rank
  17.             if self.rank[root_u] > self.rank[root_v]:
  18.                 self.parent[root_v] = root_u
  19.             elif self.rank[root_u] < self.rank[root_v]:
  20.                 self.parent[root_u] = root_v
  21.             else:
  22.                 self.parent[root_v] = root_u
  23.                 self.rank[root_u] += 1
  24.  
  25. def find_visible_profiles(connection_nodes, connection_edges, connection_from, connection_to, queries):
  26.     # Initialize Union-Find structure
  27.     uf = UnionFind(connection_nodes + 1)  # Assuming nodes are 1-indexed
  28.    
  29.     # Union the connections
  30.     for u, v in zip(connection_from, connection_to):
  31.         uf.union(u, v)
  32.    
  33.     # Count the size of each connected component
  34.      comp * (connection_nodes + 1)
  35.     for node in range(1, connection_nodes + 1):
  36.         root = uf.find(node)
  37.         component_size[root] += 1
  38.    
  39.     # Prepare results for queries
  40.     result = []
  41.     for query in queries:
  42.         root = uf.find(query)
  43.         result.append(component_size[root] if component_size[root] > 0 else 1)
  44.    
  45.     return result