fork download
  1. def merge_all_intersecting(sets):
  2. # merge all (i, end) sets into i-th set for all possible i indices
  3. for i in range(len(sets) - 2, -1, -1):
  4. # invariant: (i, end) sets are disjoint
  5. for j in range(len(sets) - 1, i, -1):
  6. if not sets[i].isdisjoint(sets[j]): # intersecting sets
  7. sets[i].update(sets[j]) # merge j-th into i-th set
  8. sets.pop(j) # remove merged set
  9.  
  10.  
  11. sets = eval(input())
  12. merge_all_intersecting(sets)
  13. print(sets)
Success #stdin #stdout 0.04s 9320KB
stdin
[ {1, 2}, {2, 3}, {3, 4}, {10, 11, 12}, {10, 13}, {20, 21} ]
stdout
[{1, 2, 3, 4}, {10, 11, 12, 13}, {20, 21}]