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

F - Close Group Editorial by CoderAnshu

Let $$dp[mask]$$ deonte the minimum number of components for $$mask$$ subset of nodes if they are forming valid clique components.
Precomputation : Now, for all $$2^{n}$$ subsets we calculate if this subset of nodes form a valid clique or not in $$O(n^{2}*2^{n})$$ using adjacency matrix of the graph, i.e $$good[mask] = true$$ if mask is forming a valid clique and false otherwise.
Intially, $$dp[0] = 0$$ and all other $$dp[i] = INF$$, now we iterate on every mask and for every mask if $$good[mask] = true$$, then obviously $$dp[mask] = 1$$ , else we iterate over all of its submasks and sum up the $$dp's$$ of the two partitions thus formed and take the minimum over it to calculate $$dp[mask]$$. Our final answer is $$dp[(1<<n)-1]$$.
The overall time complexity is $$O(n^{2}*2^{n} + 3^{n})$$.