Union find implementation using Python
Solution that runs in O(n) time def indices_dict(lis): d = defaultdict(list) for i,(a,b) in enumerate(lis): d[a].append(i) d[b].append(i) return d def disjoint_indices(lis): d = indices_dict(lis) sets = [] while len(d): que = set(d.popitem()[1]) ind = set() while len(que): ind |= que que = set([y for i in que for x in lis[i] for y in d.pop(x, … Read more