[(1, 2, 3), (2, 4, 5)] would result in a graph like this: 1 - 2 - 3 \ 4 - 5 Building the (undirected) graph would take linear time, and once it i

[(1, 2, 3), (2, 4, 5)] would result in a graph like this: 1 - 2 - 3 \ 4 - 5 Building the (undirected) graph would take linear time, and once it is built, you can do a simple Depth First Search to mark all the connected components.