0
$\begingroup$

Assume there is a Shopping Mall x and all the roads in the city are one way such that, irrespective of the path you take starting from x, you will always end up at vertex x. Device an algorithm to test the same.

This seems to be the opposite of a mother vertex, where x is reachable from all vertices instead of all vertices being reachable from x. One way I can think of solving it is to perform DFS on all the vertices and check whether x is visited.

An alternate solution which I'm not very sure of, would be to perform the Kosaraju's strongly connected algorithm and prove that there is only 1 connected component. As the question dictates that irrespective of the path you take, you always end up at x, would mean that every vertex would eventually, connect to a vertex connecting to x followed by x itself.

Is this intuition correct?

$\endgroup$
  • 1
    $\begingroup$ Do you want that all (infinite) paths from x to actually reach x or do you want x is reachable from any vertex reachable from x? These are different: even if x is reachable from all vertices reachable from x, there may be an infinite path starting at x that ends up in a cycle that does not contain x and therefore never returns to x. $\endgroup$ – Discrete lizard Apr 30 at 6:30
  • $\begingroup$ 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/ This would imply you can get to x from all vertices. I'm also obviously assuming the graph is finite $\endgroup$ – Gary Andrews30 Apr 30 at 7:52
  • $\begingroup$ A can walk a path of infinite length on a finite graph if the graph contains a cycle. But I guess you're looking for simple paths. $\endgroup$ – Discrete lizard Apr 30 at 7:58
  • 1
    $\begingroup$ The question is unclear. What does "always end up at $x$" mean? If it means that every maximal directed path has $x$ at its head, you get one answer. If it means that every maximal directed path includes $x$, you get a different answer. Suppose the road map is an oriented cycle: if I start anywhere and keep driving, I must eventually reach the mall, but I could stop driving before I get there (probably doesn't count), or I could keep going beyond it. Without pinning down a precise definition of the problem, we can't begin to produce an algorithm. $\endgroup$ – David Richerby Apr 30 at 9:29
  • 1
    $\begingroup$ Please add a reference to the original problem. $\endgroup$ – Apass.Jack Apr 30 at 12:20
1
$\begingroup$

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:

  1. Read input and initialize two adjacency lists (right and reverse edge directions): $O(N + M)$
  2. Execute dfs from $x$ using right edge directions and mark visited nodes ($A$): $O(N + M)$
  3. Execute dfs from $x$ using reverse edge directions and mark visited nodes ($B$): $O(N + M)$
  4. 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.

#include <iostream>
#include <vector>
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
    }
}

int main()
{
    // 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";
        return(0);
    }
    cout << "YES\n";
    return(0);
}

I would like to note two facts:

  1. 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.
  2. 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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.