Contest Duration: - (local time) (100 minutes) Back to Home

## F - Lights Out on Connected Graph Editorial by evima

$$G = (V,E)$$ is good if and only if $$G$$ is a connected bipartite graph.

For $$S \subseteq V$$, let $$f(S)$$ be the number of ways to remove some edges from $$G[S]$$, the subgraph induced in $$G$$ by $$S$$, so that the resulting graph $$G[S]^{\prime}$$ is a connected bipartite graph. We are done if we can find $$f(V)$$, but it is hard to compute $$f$$ directly, so let us introduce a supplementary function.

For $$S \subseteq V$$, let $$g(S)$$ be the sum of the number of ways to paint $$G[S]^{\prime}$$ using two colors over all graphs $$G[S]^{\prime}$$ that can result from removing some edges in $$G[S]$$, the subgraph induced in $$G$$ by $$S$$.

We can compute $$g$$ by finding the number of ways to paint the vertices black, white, or grey and then remove edges so that every remaining edge connects a black vertex and a white vertex. $$f(S)$$ can be found by subtracting from $$g(S)$$ the number of the colorings where $$S$$ is disconnected, then dividing the result by $$2$$.

We can compute $$f$$ in the order from the empty set to $$V$$. When properly implemented, it takes $$O(2^N M + 3^N)$$ time, which is fast enough.

posted:
last update: