Partitioning a graph with specific constraints
It suffices to be able to identify case&nbsp;B, since a graph satisfies case&nbsp;A if, and only if, its complement satisfies&nbsp;B.

A graph satisfies case&nbsp;B if, and only if, it is composed of components of size $n_1, \dots, n_\ell$ and there is some set $S\subset \{1, \dots, \ell\}$ such that $\sum_{i\in S} n_i = \sum_{j\notin S} n_j$.  (If $n_1 + \dots + n_\ell$ is odd, this is impossible, so include a fake component of size&nbsp;$1$.)

This is the set partition problem.  Bad news! It's NP-complete.  Good news!  It's not strongly NP-complete and we're encoding the numbers&nbsp;$n_i$ in unary. This means that the pseudopolynomial algorithms described on the Wikipedia page are actually polynomial-time algorithms in your context.  By checking the algorithms carefully, you can probably avoid the "fake component" trick.