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

Question

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.

Answer 1

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

• user1325120: Can u please clarify this, because if i add vertices it would be the opposite of the problem.
• user1325120: As far as I understand if we start from a disconnected graph, and adding vertices using union find until we have a component of n/2 size??
• Yuval Filmus: I'm only giving a hint since it's your exercise rather than mine. The best way to see if you understood the hint correctly is to solve the exercise.