Starry Sky Parade

The last added vertex was connected either to every previous vertex or to none of them. Therefore, when $S$ vertices remain, we can remove a vertex of degree $S-1$ or degree $0$. Repeating this until one vertex remains reconstructs the insertion order and the operation used for every inserted vertex in reverse.

We can implement the removal process efficiently. Let $D_v$ be the degree of vertex $v$ in the original graph, and let $C$ be the number of removed universal vertices. Every removed universal vertex was adjacent to every vertex that still remains, while every removed isolated vertex was adjacent to none of them. Thus, the current degree of every remaining vertex $v$ is

$$D_v-C.$$

When $S$ vertices remain, we may remove either of the following.

• A vertex with $D_v=C$ is currently isolated.
• A vertex with $D_v=C+S-1$ is currently universal.

Place the vertices into buckets by their original degrees. The required vertex can then be removed in $O(1)$ per step. One of the two kinds is always available because every input satisfies the condition. Including the computation of the initial degrees, reconstruction takes $O(N+M)$ time.

Now follow the removal history in reverse and assign brightnesses. Give the first vertex brightness

$$\left\lceil\frac N2\right\rceil.$$

Let $L$ and $R$ be the minimum and maximum brightness assigned so far.

• For an isolated vertex, assign $N-R$. Its sum with every existing brightness is at most $N$, so it creates no edge.
• For a universal vertex, assign $N-L+1$. Its sum with every existing brightness is greater than $N$, so it is connected to every existing vertex.

It remains to show that every brightness lies between $1$ and $N$. The invariant

$$L+R\in\{N,N+1\}$$

holds after every step. Also, adding one vertex increases $R-L$ by at most one, so $R-L\leq N-1$ throughout the construction. Together, these properties imply $L\geq1$ and .

The time complexity is $O(N+M)$, and the space complexity is also $O(N+M)$.

Solution written by GPT6