Efficiently check if any vertex has a path to its partner vertex
Observation: Each weakly connected component can contain at most 1 cycle, and every vertex in such a cycle is reachable from every vertex in the weakly connected component.  That's because every vertex that participates in a cycle exhausts its single out-edge by connecting to the next vertex in the cycle, so the only other edges that can be incident on any vertex in this cycle must be in-edges from other vertices.

In more detail: Suppose to the contrary that a single component contains 2 cycles: Then either they are vertex-disjoint or not.  In the former case, there must be an undirected path of edges (i.e., a path in the graph where edge orientation has been forgotten) connecting the two cycles.  But the first and last edges in this undirected path must be "outwards" (i.e., the first must be an in-edge to the first cycle, and the last must be an in-edge to the second cycle), implying that some vertex on the path must have 2 out-edges, so this case cannot happen.  In the latter case, let the two cycles be $C_1$ and $C_2$, and w.l.o.g. suppose $|C_1| \geq |C_2|$.  Let $uv$ be an edge in $C_1$ such that $u \in C_1 \cap C_2$ but $v \notin C_2$.  (Such an edge must exist if $C_1 \neq C_2$.)  Then $u$ must have a successor $w \neq v$ in $C_2$; but this immediately implies that $u$ has outdegree at least 2, so this cannot happen either.

Algorithm phase 1: Detecting a cycle

So, starting at any vertex and successively traversing the single out-edge can only give one of two possible outcomes:


We reach a vertex with no out-edge.  In this case, the component has no cycle.
We reach a vertex we have seen before.  In this case, the component has a single cycle consisting of all vertices visited since the last time the final vertex was visited.  In a $k$-vertex component, the cycle vertices can be identified in $O(k)$ time by numbering the vertices in visitation order and gathering them together in a subsequent pass.


To simplify notation I'll label the vertices with positive and negative integers, instead of upper- and lower-case letters.  We will maintain a counter $c_i$ for each pair of vertices $i, -i$: at the end of the algorithm, $c_i = 2$ if and only if at least one of the vertices $i$ and $-i$ can reach the other by some path.

If a cycle was detected, we can start at any vertex in the cycle and continue following out-edges until we hit the first vertex again, incrementing $c_{|i|}$ for each vertex $i$ encountered.  Also, we (at least conceptually) create a new vertex $x$ to represent "the cycle", and as we proceed through each vertex $v$ in the cycle, we change every non-cycle edge $uv$ to $ux$.  (Conceptually) delete the cycle vertices, and set $z = x$.

If no cycle was detected, set $z$ to the last vertex we found, say $i$, which by construction has no out-edge.  Increment $c_i$.

Observe that since any cycle has been deleted, the component is now a tree with all edges directed toward $z$.

Algorithm phase 2: Reverse DFS

We now perform a DFS starting at $z$ and proceeding "against" the direction of each edge.  During this traversal:


Upon entering a vertex $i$: If $c_{|i|} &lt; 2$, then increment it.
Upon leaving a vertex $i$: If $c_{|i|} = 1$, then decrement it.


This asymmetric increment/decrement scheme ensures that, whenever we discover a path from the root $z$ that contains both vertices in a pair, the discovery (which is recorded as a count of 2) "sticks", while OTOH whenever we discover that no path from the root $z$ through some vertex $i$ also contains $-i$, the discovery of $i$ is "forgotten" -- this has the important effect of not recording as matched any pair $i, -i$ that occur in the same component but such that neither is the ancestor of the other.

The above can all be implemented to take linear time in the number of edges within a component, so the overall time to process the graph is $O(|V|+|E|)$.