My goal is to algorithmically take a list of relations between nodes (in other words, a list of undirected edges between nodes of a graph) and label each group of nodes such that all nodes that have a path between them have the same label (I believe the term for this is a "connected component") and nodes that do not have a path between them have different labels. Put another way, each connected component has a unique label.

NOTE: I haven't done all that much in the way of discrete math proofs since college, so hopefully you can bear with me and correct my terminology/methods if necessary.

To clarify, the data is in the form of a list of pairs of connected nodes.

For example:

n_1, n_3
n_3, n_5
n_5, n_7
n_5, n_9
n_2, n_4
n_4, n_6

In this <contrived> example, the odd-numbered nodes all belong to the same group, and the even-numbered nodes belong to another group.

I believe the way to do this is to process each item in the list according to the following rules:

• Maintain an ordered list (call it "encounteredNodes") of all encountered nodes and the group label they have been assigned to
• Maintain an integer variable (call it "nextLabel") that is incremented and returned each time a new unique label is needed
• For each item in the list, determine if either node has been encountered yet.
  • If neither node has been encountered, get a new unique label from nextLabel and add both the nodes to encounteredNodes with this new uniqueLabel
  • If one node has been encountered but not the other, assign the label of the previously-encountered node to that of the unencountered node.
  • If both nodes have been previously encountered, take the lesser label of the two and use it to replace the label of all nodes in encounteredLabels that have the greater label of the two.

After one pass of this "for loop" through all the nodes, the algorithm is complete and the nodes have been grouped according to the goal. I believe the proof can be shown in this way:

Lemma 1: None of the operations can result in 2 previously encountered nodes that already have the same label being assigned to different labels. Because of this, already encountered nodes never "split off" from their group of nodes with the same labels, and once two nodes have the same label, they will never have differing labels (though they may change together to the same new label) for the remainder of the algorithm.

Assume there are two nodes that have a path between them via the list of edges, yet after the algorithm finishes, they have different labels (call them $L_1$ and $L_2$. If that's the case, then either...

1. They each contain a node (and these two nodes are directly connected), or...
2. there is a "chain" formed of groups of nodes where each group has the same label and the chain can be traversed to get from $L_1$ to $L_2$.

However neither of these scenarios can occur based on the algorithm. In the case of 1, there would have to have been a pair of connected nodes in the list where one node belongs to $L_1$ and one node belongs to $L_2$. However, after the algorithm processed this connection, both nodes would have the same label, and because of Lemma 1, they would have the same label until the end of the algorithm. In the case of 2, the neighbouring links in the chain could not exist because of the first case. Thus. This is a proof by contradiction.

Is this all sound? Also, I was never that great at algorithm runtime calculations, but I think it would be $O(n \log{n})$ because iterating the list of connections is linear time, but each iteration requires a search of ordered lists. Is this correct?