Algorithm and proof for combining a list of node connections into groups of nodes efficiently
You should look into DFS and BFS, which can solve this problem in $O(n+m)$ time where $n$ is the number of nodes and $m$ is the number of edges.

The performance of the algorithm you described is much worse than you think, because you potentially have to relabel nodes many times. Consider the edges presented in this order:

$v_{2k},v_{2k+1}$

$\vdots$

$v_2, v_3$

$v_0, v_1$

$v_{2k}, v_{2k-1}$

$\vdots$

$v_3, v_4$

$v_2, v_1$

The introduction of the edge $v_{2k}, v_{2k-1}$ requires relabeling $v_{2k}$ and $v_{2k+1}$, introducing $v_{2k-2}, v_{2k-3}$ requires relabeling $v_{2k-2}, v_{2k-1}, v_{2k}$ and $v_{2k+1}$. Finally, introducing $v_2,v_1$ requires relabeling $v_2,\ldots,v_{2k+1}$. This ends up being quadratic in $n+m$.

The idea behind your algorithm is somewhat valid though, and you can implement it much more efficiently using the Union-Find data structure which, if you will, can "defer" the relabeling.