Pre-Requisites : DP + Bitmasking

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})\).

Sample Code (C++)