fork(1) download
copy 
  1. from collections import defaultdict
  2.  
  3.  
  4. class UnionFind:
  5.     """
  6.     Detailed info on union find data structure can be found at:
  7.         http://a...content-available-to-author-only...n.edu/15uf/
  8.     Complexity of merge is O(log*n), not O(logn). Detailed info can be found at:
  9.         https://e...content-available-to-author-only...a.org/wiki/Iterated_logarithm
  10.     """
  11.     def __init__(self, size):
  12.         self.parent = [i for i in range(size)]
  13.         self.size = [1] * size
  14.  
  15.     def _root(self, a):
  16.         while self.parent[a] != a:
  17.             self.parent[a] = self.parent[self.parent[a]]
  18.             a = self.parent[a]
  19.         return a
  20.  
  21.     def merge(self, a, b):
  22.         a, b = self._root(a), self._root(b)
  23.         if self.size[a] < self.size[b]:
  24.             a, b = b, a
  25.         self.parent[b] = a
  26.         self.size[a] += self.size[b]
  27.  
  28.     def __repr__(self):
  29.         ret = defaultdict(list)
  30.         for i in range(len(self.parent)):
  31.             ret[self._root(i)].append(i)
  32.         return "\n".join(str(v) for k, v in ret.items())
  33.  
  34.  
  35. def find_same_contacts(contacts):
  36.     """
  37.     For each contact in contacts
  38.         For each element in contact
  39.             If element exists at seen_keys, merge contacts
  40.             Otherwise add element to seen_keys with contact id as value
  41.     Complexity is O(nlog*n)
  42.     """
  43.     union_find = UnionFind(len(contacts))
  44.     seen_keys = {}
  45.     for i, contact in enumerate(contacts):
  46.         for elem in contact:
  47.             if elem in seen_keys:
  48.                 union_find.merge(seen_keys[elem], i)
  49.             else:
  50.                 seen_keys[elem] = i
  51.     print(union_find)
  52.  
  53.  
  54. the_contacts = [["Gaurav", "gaurav@gmail.com", "gaurav@gfgQA.com"],
  55.                      ["Lucky", "lucky@gmail.com", "+1234567"],
  56.                      ["gaurav123", "+5412312", "gaurav123@skype.com"],
  57.                      ["gaurav1993", "+5412312", "gaurav@gfgQA.com"],
  58.                      ["raja", "+2231210", "raja@gfg.com"],
  59.                      ["bahubali", "+878312", "raja"]]
  60.  
  61. find_same_contacts(the_contacts)
Success #stdin #stdout 0.04s 10240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[1]
[0, 2, 3]
[4, 5]
https://ideone.com/7vKTLx
language:
Python 3 (python  3.9.5)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!