lst = [[1,2,3], [10,5], [3,8,5]]
lookup = {}
out = []
index = 0
for grp in lst:
keys = [lookup.get(num, None) for num in grp]
keys = [key for key in keys if key is not None]
if len(keys):
if len(set(keys)) != 1:
for num in grp:
out[keys[0]].append(num)
seen = set()
keys = [key for key in keys if key not in seen and not seen.add(key)]
for key in keys[1:]:
out[keys[0]].extend(out[key])
del out[key]
seen = set()
out[keys[0]] = [item for item in out[keys[0]] if item not in seen and not seen.add(item)]
else:
for num in grp:
lookup[num] = keys[0]
out[keys[0]].extend(grp)
seen = set()
out[keys[0]] = [item for item in out[keys[0]] if item not in seen and not seen.add(item)]
else:
out.append(grp)
for num in grp:
lookup[num] = index
index += 1
print out
assert out == [[1, 2, 3, 10, 5, 8]]
bHN0ID0gW1sxLDIsM10sIFsxMCw1XSwgWzMsOCw1XV0KCmxvb2t1cCA9IHt9Cm91dCA9IFtdCmluZGV4ID0gMApmb3IgZ3JwIGluIGxzdDoKICAgIGtleXMgPSBbbG9va3VwLmdldChudW0sIE5vbmUpIGZvciBudW0gaW4gZ3JwXQogICAga2V5cyA9IFtrZXkgZm9yIGtleSBpbiBrZXlzIGlmIGtleSBpcyBub3QgTm9uZV0KICAgIGlmIGxlbihrZXlzKToKICAgICAgICBpZiBsZW4oc2V0KGtleXMpKSAhPSAxOgogICAgICAgICAgICBmb3IgbnVtIGluIGdycDoKICAgICAgICAgICAgICAgIG91dFtrZXlzWzBdXS5hcHBlbmQobnVtKQogICAgICAgICAgICBzZWVuID0gc2V0KCkKICAgICAgICAgICAga2V5cyA9IFtrZXkgZm9yIGtleSBpbiBrZXlzIGlmIGtleSBub3QgaW4gc2VlbiBhbmQgbm90IHNlZW4uYWRkKGtleSldCiAgICAgICAgICAgIGZvciBrZXkgaW4ga2V5c1sxOl06CiAgICAgICAgICAgICAgICBvdXRba2V5c1swXV0uZXh0ZW5kKG91dFtrZXldKQogICAgICAgICAgICAgICAgZGVsIG91dFtrZXldCiAgICAgICAgICAgIHNlZW4gPSBzZXQoKQogICAgICAgICAgICBvdXRba2V5c1swXV0gPSBbaXRlbSBmb3IgaXRlbSBpbiBvdXRba2V5c1swXV0gaWYgaXRlbSBub3QgaW4gc2VlbiBhbmQgbm90IHNlZW4uYWRkKGl0ZW0pXQogICAgICAgIGVsc2U6CiAgICAgICAgICAgIGZvciBudW0gaW4gZ3JwOgogICAgICAgICAgICAgICAgbG9va3VwW251bV0gPSBrZXlzWzBdCiAgICAgICAgICAgIG91dFtrZXlzWzBdXS5leHRlbmQoZ3JwKQogICAgICAgICAgICBzZWVuID0gc2V0KCkKICAgICAgICAgICAgb3V0W2tleXNbMF1dID0gW2l0ZW0gZm9yIGl0ZW0gaW4gb3V0W2tleXNbMF1dIGlmIGl0ZW0gbm90IGluIHNlZW4gYW5kIG5vdCBzZWVuLmFkZChpdGVtKV0KICAgIGVsc2U6CiAgICAgICAgb3V0LmFwcGVuZChncnApCiAgICAgICAgZm9yIG51bSBpbiBncnA6CiAgICAgICAgICAgIGxvb2t1cFtudW1dID0gaW5kZXgKICAgICAgICBpbmRleCArPSAxCnByaW50IG91dAphc3NlcnQgb3V0ID09IFtbMSwgMiwgMywgMTAsIDUsIDhdXQ==