# Deleting vertices so that largest connected component has at most $n/2$ vertices

I have a question regarding a graph algorithm which is as follows:

Given a graph $G = (V,E)$ whose vertices are uniquely labeled $\{1, 2,\dots ,n\}$ we want to determine the smallest integer $k$ such that deleting vertices $1$ through $k$ results in a graph whose largest connected component has at most $n/2$ vertices (when we delete a vertex we also delete all edges incident to that vertex). Give an $O(m \log^* n)$ algorithm that determines $k$.

The graph at the beginning could be disconnected, nor at the end need it be connected. Since $O(m \log^*n)$ is almost linear, $\log^*n$ grows very very slowly like in union-find data structure so this algorithm is almost linear time like union-find. I am trying to solve it through union find but it seems I am doing something wrong. Now I think that I should use union-find as a black box, but I ca'nt figure it out.

This is a practice problem, not homework.

Hint: Try working backwards, adding vertices to the graph in reverse order $n,\dots,1$.