I still don't really understand the question (what kind of conditions do you care about? Theoretical? Algorithmic?) but here are some thoughts. $A$ is the adjacency matrix of a directed graph, and conjugating $A$ by a permutation just corresponds to relabeling the vertices. What you want is more or less to compute the connected components of the underlying undirected graph, or at least to determine whether there is one or more than one such component.
Probably there are many algorithms to do this efficiently; here's two off the top of my head.
Compute $B = (A + A^T)^{2^k}$ by repeated squaring, where $k$ is the smallest positive integer such that $2^k \ge n$. Then check whether at least one entry in $B$ is equal to zero. (If the entries of the matrices get large enough to be annoying, at any step you can replace all positive entries by $1$.)
Compute the Laplacian matrix $\Delta$ of the underlying undirected graph. $\dim \ker \Delta$ is equal to the number of connected components, and this can be efficiently computed by row reduction.
To address the problem that the OP actually wanted solved:
Given two symmetric positive definite matrices $C$ and $D$, show that $CD+DC$ is also positive definite.
This is not true, as can be seen from the following example:
$$C = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}, \quad D = \begin{bmatrix} 100 \\ & 1 \end{bmatrix}.$$
Then their respective spectra are:
$$\sigma(C) = \{1,3\}, \quad \sigma(D) = \{1, 100\}, \quad \sigma(CD+DC) \approx \{-20.2724, 424.272 \}.$$
The reason is simple: when computing $\det(CD+DC)$, the big factor $100$ participates in the positive part only $2$ times, but squared in the negative (counter-diagonal) part.
This might give you some insight how things behave in a more general setting. For example, I'm fairly certain that it can be shown that the following is true: if $C$ and $D$ do not commute, there exists $n \in \mathbb{N}$ such that $CD^n+D^nC$ is not positive definite. All you need to do is observe a $2 \times 2$ submatrix for which $D$ is not a multiply of $I_2$ (WLOG, you can assume that $D$ is diagonal). In other words, any such $D$ can be blown enough to make the above invalid.
This would give you that for every symmetric positive definite $C$ (such that it is not a multiple of identity), you can find a symmetric positive definite $D$ (diagonal, if you want) such that the above does not hold.
Best Answer
Since $B$ is rank one and positive-semi-definite (has to be p.s.d. and not p.d. since it is rank deficient) matrix, you have $B = u u^{T}$ for some $u \neq 0$. And so using $\mathrm{tr}(Auu^T) =\mathrm{tr}(u^TAu) = 0$, it follows that $u$ is an isotropic vector of $A$.
EDIT: Thanks to Loup Blanc for pointing out the mistake.