# Checking if all nodes are reachable in a oriented graph from all other nodes

I'm having a lot of troubles understanding a preparation exercise about oriented graphs:

Consider the following game played on a directed graph G = (V, E) with n nodes and m edges. A pawn is initially placed on node s. The pawn can be moved from its current position u to a node v if there exists a directed edge (u, v) ∈ E in G. Additionally, there is a set of special nodes X ⊆ V. If the pawn is on a special node x ∈ X, it can also be moved along incoming edges to x, in addition to the outgoing edges from x. In other words, the pawn can be moved from x to v if and only if (v, x) ∈ E or (x, v) ∈ E, or both.

Design an algorithm that, in O(m + n) time, decides whether, regardless of the initial position s, it is always possible to move the pawn from s to any other node t in the graph with an appropriate sequence of moves.

I really don't understand where to begin to solve this problem.

Here is what i know: i need to find if the graph is connected, which would be very easy with a BFS visit. The fact that the problem asks for a O(m+n) solution means that i need to use BFS somewhere. What makes it complicated to me is the condition that there are special nodes where the pawn can be moved through incoming edges.

Can anyone help me on this? I just need some advice on how to go forward with this problem

One way to deal with having these special vertices is to create a reversed graph from your original graph, which can be done in $$O(n+m)$$ time, assuming you are using adjacency list representation. This reversed graph contains all vertices but with the direction of the edges flipped. When you traverse the original graph and you encounter a special vertex you will also visit its neighbours in the reverse graph.
• You are not going to continue the visit on the reversed graph if you encounter a special vertex. Rather you will only consider the neighbourhood of vertex $u$ in the reversed graph during traversal. That is, if $v$ is a neighbor of $u$ in the reversed graph, you will visit $v$ in the original graph. Jul 16, 2023 at 15:18