Given n tuples representing pairs, return a list with connected tuples
You can solve it with Disjoint Set (Union-Find) implementation.
Initialize the structure djs
with all of the numbers. Then for each tuple (x,y)
, call djs.merge(x,y)
. Now for each number x
, create a new set for it iff djs.sameSet(x,)==false
for an arbitrary y
from each existing set.
Maybe that could help you.
You also could use networkx as a dependency.
import networkx as nx
pairs = [(1,62),
(1,192),
(1,168),
(64,449),
(263,449),
(192,289),
(128,263),
(128,345),
(3,10),
(10,11)]
G = nx.Graph()
G.add_edges_from(pairs)
list(nx.connected_components(G))