回答編集履歴

+ (追記)

+ もっと素直に組んでみました

+ ```python

+ def unify_group2(all_groups: List[Set[int]]) -> List[Set[int]]:

+ val_to_index = {}

+ result = []

+

+ for s in all_groups:

+ indices = {val_to_index.get(n, -1) for n in s}

+ if max(indices) == -1:

+ result.append(s)

+ index = len(result) - 1

+ for n in s:

+ val_to_index[n] = index

+ else:

+ indices = sorted(i for i in indices if i > -1)

+ index = indices[0]

+ for i in indices[1:]:

+ result[index] |= result[i]

+ for j in result[i]:

+ val_to_index[j] = index

+ # 空をセットしておいて後で取り除く

+ result[i] = {}

+ result[index] |= s

+ for n in s:

+ val_to_index[n] = index

+

+ return list(filter(None, result))

+ ```

+ ----

+