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 componen

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).