fork(4) download
copy 
  1. def connected_tuples(pairs):
  2.     # for every element, we keep a reference to the list it belongs to
  3.     lists_by_element = {}
  4.  
  5.     def make_new_list_for(x, y):
  6.         lists_by_element[x] = lists_by_element[y] = [x, y]
  7.  
  8.     def add_element_to_list(lst, el):
  9.         lst.append(el)
  10.         lists_by_element[el] = lst
  11.  
  12.     def merge_lists(lst1, lst2):
  13.         merged_list = lst1 + lst2
  14.         for el in merged_list:
  15.             lists_by_element[el] = merged_list
  16.  
  17.     for x, y in pairs:
  18.         xList = lists_by_element.get(x)
  19.         yList = lists_by_element.get(y)
  20.  
  21.         if not xList and not yList:
  22.             make_new_list_for(x, y)
  23.  
  24.         if xList and not yList:
  25.             add_element_to_list(xList, y)
  26.  
  27.         if yList and not xList:
  28.             add_element_to_list(yList, x)            
  29.  
  30.         if xList and yList and xList != yList:
  31.             merge_lists(xList, yList)
  32.  
  33.     # return the unique lists present in the dictionary
  34.     return set(tuple(l) for l in lists_by_element.values())
  35.  
  36.  
  37. pairs = [(1,62),
  38.     (1,192),
  39.     (1,168),
  40.     (64,449),
  41.     (263,449),      
  42.     (192,289),
  43.     (128,263),
  44.     (128,345),
  45.     (3,10),
  46.     (10,11)
  47.     ]
  48.  
  49. print connected_tuples(pairs)
  50.  
Success #stdin #stdout #stderr 0.04s 42064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
set([(1, 62, 192, 168, 289), (64, 449, 263, 128, 345), (3, 10, 11)])
stderr
copy 
Warning: cannot find your CPU L2 cache size in /proc/cpuinfo
https://ideone.com/tz9t7m
language:
Python (PyPy 2.7.13)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!