from collections import defaultdict
class UnionFind:
"""
Detailed info on union find data structure can be found at:
http://a...content-available-to-author-only...n.edu/15uf/
Complexity of merge is O(log*n), not O(logn). Detailed info can be found at:
https://e...content-available-to-author-only...a.org/wiki/Iterated_logarithm
"""
def __init__(self, size):
self.parent = [i for i in range(size)]
self.size = [1] * size
def _root(self, a):
while self.parent[a] != a:
self.parent[a] = self.parent[self.parent[a]]
a = self.parent[a]
return a
def merge(self, a, b):
a, b = self._root(a), self._root(b)
if self.size[a] < self.size[b]:
a, b = b, a
self.parent[b] = a
self.size[a] += self.size[b]
def __repr__(self):
ret = defaultdict(list)
for i in range(len(self.parent)):
ret[self._root(i)].append(i)
return "\n".join(str(v) for k, v in ret.items())
def find_same_contacts(contacts):
"""
For each contact in contacts
For each element in contact
If element exists at seen_keys, merge contacts
Otherwise add element to seen_keys with contact id as value
Complexity is O(nlog*n)
"""
union_find = UnionFind(len(contacts))
seen_keys = {}
for i, contact in enumerate(contacts):
for elem in contact:
if elem in seen_keys:
union_find.merge(seen_keys[elem], i)
else:
seen_keys[elem] = i
print(union_find)
the_contacts = [["Gaurav", "gaurav@gmail.com", "gaurav@gfgQA.com"],
["Lucky", "lucky@gmail.com", "+1234567"],
["gaurav123", "+5412312", "gaurav123@skype.com"],
["gaurav1993", "+5412312", "gaurav@gfgQA.com"],
["raja", "+2231210", "raja@gfg.com"],
["bahubali", "+878312", "raja"]]
find_same_contacts(the_contacts)
ZnJvbSBjb2xsZWN0aW9ucyBpbXBvcnQgZGVmYXVsdGRpY3QKCgpjbGFzcyBVbmlvbkZpbmQ6CiAgICAiIiIKICAgIERldGFpbGVkIGluZm8gb24gdW5pb24gZmluZCBkYXRhIHN0cnVjdHVyZSBjYW4gYmUgZm91bmQgYXQ6CiAgICAgICAgaHR0cDovL2EuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLm4uZWR1LzE1dWYvCiAgICBDb21wbGV4aXR5IG9mIG1lcmdlIGlzIE8obG9nKm4pLCBub3QgTyhsb2duKS4gRGV0YWlsZWQgaW5mbyBjYW4gYmUgZm91bmQgYXQ6CiAgICAgICAgaHR0cHM6Ly9lLi4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5hLm9yZy93aWtpL0l0ZXJhdGVkX2xvZ2FyaXRobQogICAgIiIiCiAgICBkZWYgX19pbml0X18oc2VsZiwgc2l6ZSk6CiAgICAgICAgc2VsZi5wYXJlbnQgPSBbaSBmb3IgaSBpbiByYW5nZShzaXplKV0KICAgICAgICBzZWxmLnNpemUgPSBbMV0gKiBzaXplCiAgICAgICAgCiAgICBkZWYgX3Jvb3Qoc2VsZiwgYSk6CiAgICAgICAgd2hpbGUgc2VsZi5wYXJlbnRbYV0gIT0gYToKICAgICAgICAgICAgc2VsZi5wYXJlbnRbYV0gPSBzZWxmLnBhcmVudFtzZWxmLnBhcmVudFthXV0KICAgICAgICAgICAgYSA9IHNlbGYucGFyZW50W2FdCiAgICAgICAgcmV0dXJuIGEKICAgIAogICAgZGVmIG1lcmdlKHNlbGYsIGEsIGIpOgogICAgICAgIGEsIGIgPSBzZWxmLl9yb290KGEpLCBzZWxmLl9yb290KGIpCiAgICAgICAgaWYgc2VsZi5zaXplW2FdIDwgc2VsZi5zaXplW2JdOgogICAgICAgICAgICBhLCBiID0gYiwgYQogICAgICAgIHNlbGYucGFyZW50W2JdID0gYQogICAgICAgIHNlbGYuc2l6ZVthXSArPSBzZWxmLnNpemVbYl0KCiAgICBkZWYgX19yZXByX18oc2VsZik6CiAgICAgICAgcmV0ID0gZGVmYXVsdGRpY3QobGlzdCkKICAgICAgICBmb3IgaSBpbiByYW5nZShsZW4oc2VsZi5wYXJlbnQpKToKICAgICAgICAgICAgcmV0W3NlbGYuX3Jvb3QoaSldLmFwcGVuZChpKQogICAgICAgIHJldHVybiAiXG4iLmpvaW4oc3RyKHYpIGZvciBrLCB2IGluIHJldC5pdGVtcygpKQoKCmRlZiBmaW5kX3NhbWVfY29udGFjdHMoY29udGFjdHMpOgogICAgIiIiCiAgICBGb3IgZWFjaCBjb250YWN0IGluIGNvbnRhY3RzCiAgICAgICAgRm9yIGVhY2ggZWxlbWVudCBpbiBjb250YWN0CiAgICAgICAgICAgIElmIGVsZW1lbnQgZXhpc3RzIGF0IHNlZW5fa2V5cywgbWVyZ2UgY29udGFjdHMKICAgICAgICAgICAgT3RoZXJ3aXNlIGFkZCBlbGVtZW50IHRvIHNlZW5fa2V5cyB3aXRoIGNvbnRhY3QgaWQgYXMgdmFsdWUKICAgIENvbXBsZXhpdHkgaXMgTyhubG9nKm4pCiAgICAiIiIKICAgIHVuaW9uX2ZpbmQgPSBVbmlvbkZpbmQobGVuKGNvbnRhY3RzKSkKICAgIHNlZW5fa2V5cyA9IHt9CiAgICBmb3IgaSwgY29udGFjdCBpbiBlbnVtZXJhdGUoY29udGFjdHMpOgogICAgICAgIGZvciBlbGVtIGluIGNvbnRhY3Q6CiAgICAgICAgICAgIGlmIGVsZW0gaW4gc2Vlbl9rZXlzOgogICAgICAgICAgICAgICAgdW5pb25fZmluZC5tZXJnZShzZWVuX2tleXNbZWxlbV0sIGkpCiAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICBzZWVuX2tleXNbZWxlbV0gPSBpCiAgICBwcmludCh1bmlvbl9maW5kKQoKCnRoZV9jb250YWN0cyA9IFtbIkdhdXJhdiIsICJnYXVyYXZAZ21haWwuY29tIiwgImdhdXJhdkBnZmdRQS5jb20iXSwKICAgICAgICAgICAgICAgICAgICAgWyJMdWNreSIsICJsdWNreUBnbWFpbC5jb20iLCAiKzEyMzQ1NjciXSwKICAgICAgICAgICAgICAgICAgICAgWyJnYXVyYXYxMjMiLCAiKzU0MTIzMTIiLCAiZ2F1cmF2MTIzQHNreXBlLmNvbSJdLAogICAgICAgICAgICAgICAgICAgICBbImdhdXJhdjE5OTMiLCAiKzU0MTIzMTIiLCAiZ2F1cmF2QGdmZ1FBLmNvbSJdLAogICAgICAgICAgICAgICAgICAgICBbInJhamEiLCAiKzIyMzEyMTAiLCAicmFqYUBnZmcuY29tIl0sCiAgICAgICAgICAgICAgICAgICAgIFsiYmFodWJhbGkiLCAiKzg3ODMxMiIsICJyYWphIl1dCgpmaW5kX3NhbWVfY29udGFjdHModGhlX2NvbnRhY3RzKQ==