[s_tim]

You could model the problem as a graph (each integer represents a vertex and two consecutive integers an edge, e.g. (1, 2, 3) is a graph with nodes 1,2,3 and edges between 1 and 2 and 2 and 3). Then your problem is just to find all connected components of the graph (https://en.wikipedia.org/wiki/Connected_component_(graph_the....

[Patient0]

Yeah but realising that two "nodes" of the graph are connected requires doing a set intersection, which I concluded was quite expensive to do between all possible sets. i.e. building the "graph" was an expensive operation... unless I've misunderstood you.

[s_tim]

You build from the different tuples in your list just one graph. Then it's just a simple DFS/BFS with one random start node. Which gives you your first component. Then you can get the second if you start at a node which is not in the previous component until you visited all nodes. This should all be in O(n).

[gk101]

[(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.