For an undirected graph $G$: for each partition $\{I,J\}$ of the vertices of $G$ we check if there are no edges between vertices in $I$ and vertices in $J$.
If $G$ is disconnected, then $\{I,J\}$ can be found (choose $I$ as the vertices in one connected component). Conversely, if $\{I,J\}$ can be found, then there are no edges between $I$ and $J$ and $G$ is disconnected.
For the adjacency matrix $A=(a_{ij})$, if $\{I,J\}$ can be found then subgraph formed by the rows indexed by $I$ and the columns indexed by $J$ form an all-$0$ submatrix.
This means that, $A$ has the block structure
$$\begin{array}{|c|c|}
\hline
A_I & 0 \\
\hline
0 & A_J \\
\hline
\end{array}$$ where the rows and columns are indexed by the indices in $I$ then $J$.
In the directed case, we instead have no edges directed from a vertex in $I$ to a vertex in $J$. So we can find $\{I,J\}$ if $G$ is not strongly connected (take $I$ to be the vertices in one strongly connected component).