USACO 644 Closing the Farm - Solution

$1.$ Store the closing order: e.g., remove $1$, then $3$, then $2$.

$2.$ Reverse the order: add $2$, then $3$, then $1$.

$3.$ Start with no barns open. Initialize DSU.

$4.$ Add barns in reverse order. After each addition, check if all open barns are in one component.

$5.$ Store answers, then reverse the answer array to get the original order. Time: $O(n \cdot \alpha(n))$ per barn addition. Space: $O(n)$ for DSU and the answer array.