You don't mention that visiting a vertex multiple times is not allowed so I will assume that there isn't such a restriction. In your comment on your question you state that:
The question is on the lines of If I were to start driving from X, no matter how I drive, I can always reach x
So the question is if $x$ is reachable from all nodes which are reachable by $x$. This is an easy to solve problem in linear time. First do a dfs from $x$ using the right direction of the edges to find which nodes are reachable by $x$. Let's name this set of nodes $A$. Then do a second dfs from $x$ to find from which nodes you can reach $x$. Let's name this set of nodes $B$. The answer of the problem is positive iff
$$A \subseteq B$$
You can check if this condition holds in linear time. The algorithm consists of the following steps:
- Read input and initialize two adjacency lists (right and reverse edge directions): $O(N + M)$
- Execute dfs from $x$ using right edge directions and mark visited nodes ($A$): $O(N + M)$
- Execute dfs from $x$ using reverse edge directions and mark visited nodes ($B$): $O(N + M)$
- Check whether $A \subseteq B$ or equivalently if $u \in A \Rightarrow u \in B$: $O(N)$
The total computational and space complexity of the above algorithm is $O(N + M)$ (linear), where $N = |V| \wedge M = |E|$. You may check the following C++ code if you want.
using namespace std;
#define MAXN 100005 // Maximum number of nodes + 5 (change according to your requirements)
vector<int> E[MAXN]; // Adjacency lists with right edge directions
vector<int> RE[MAXN]; // Adjacency lists with reverse edge directions
bool A[MAXN]; // A[i] will become true iff i-th node is reachable from x
bool B[MAXN]; // B[i] will become true iff x is reachable from i-th node
void dfs(int u)
A[u] = true; // u was reached from x
for (int i = 0; i < E[u].size(); i++) // for every out-neighbour of u...
int v = E[u][i]; // We name this node v
if (!A[v]) dfs(v); // If you haven't visited v yet, visit it now
void dfsr(int u)
B[u] = true; // x can be reached from u
for (int i = 0; i < RE[u].size(); i++) // for every in-neighbour of u...
int v = RE[u][i]; // We name this node v
if (!B[v]) dfsr(v); // If you haven't visited v yet, visit it now
// Read input and make initializations...
// I assume that nodes are numbered from 0 to N-1
int N, M, x;
cin >> N >> M >> x;
for (int i = 0; i < M; i++)
int u, v;
cin >> u >> v; // There is an edge from u to v
E[u].push_back(v); // Right direction from u to v
RE[v].push_back(u); // Reverse direction from v to u
dfs(x); // DFS from x using the right direction of edges
dfsr(x); // DFS from x using the revers direction of edges
// Check if A is a subset of B (A[x] => B[x])
for (int i = 0; i < N; i++) if (A[i] && !B[i])
cout << "NO\n";
cout << "YES\n";
I would like to note two facts:
- In your comment you say that the problem statement is equivalent with wether $x$ is reachable by every node. This is not true based on your previous statement. It asks if $x$ is reachable by every node reachable by $x$, which is different. If that was the case only one dfs from $x$ using the reverse edges would be required.
- On your question you proposed an idea about finding the strongly connected components. It is true that you can answer the question using this technique, but you don't have to find if there is only one strongly connected component (that solves the wrong problem - see 1.). Instead you have to verify that there is no edge from $x$'s strongly connected component to any other strongly connected component (in which case there would be nodes where you could go starting from $x$ but then you could not return to $x$ from them). This is a correct solution for your problem which also has linear time complexity. Although its implementation is a little bit harder and there is no reason to make things more complex than they are.