3 ms·
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 ed
by s_tim 10y ago
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_theory) https://en.wikipedia.org/wiki/Connected_component_(graph_the....
- Patient0 10y agoYeah 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 10y agoYou 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 10y ago[(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.