= Solution
Only arrange switches towards `A`. For every <vertex> $u$, compute its degree $\deg(u)$ and the current number $c(u)$ of neighbours preferring `A`. Put the `B` <vertices> in a <max-heap> with key $q(u)=2c(u)-\deg(u)$. Maintain each <vertex>'s current heap <array> index during exchanges.
While the queue is nonempty and its <maximum> key is positive, extract that <vertex> $u$, show it its neighbours' preferences, append $u$ to the answer sequence, and set its preference to `A`. For every neighbour $v$ still preferring `B`, increase $c(v)$ by one and use `increaseKey` to increase its heap key by two. Stop when every remaining key is nonpositive.
A positive key means precisely a strict majority of `A` neighbours, so every listed move is legal. Degrees never change; `A` neighbours never revert in this chosen sequence. An isolated `B` <vertex> has key zero and cannot be converted. Initialization costs $O(|V|+|E|)$, there are at most $|V|$ extractions, and each <edge> causes at most two neighbour inspections and at most a constant number of key updates. The required bound is therefore \b[$O((|V|+|E|)\log(|V|+1))$]. A simple work queue of newly eligible <vertices> can even implement the same <monotone threshold activation> in $O(|V|+|E|)$ time, since a <vertex> needs to be enqueued only once.
Back to article page
