0
$\begingroup$

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

$\endgroup$
1

1 Answer 1

1
$\begingroup$

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.

Also, since you have a directed graph you might want to use algorithms for testing strong connectivity

$\endgroup$
3
  • $\begingroup$ Thanks. So basically i should run a BFS visit on the original graph and when i encounter a special node with an incoming edge i should continue the visit on the reversed graph? I was thinking of using strong connectivity too, since it has a time complexity of n+m $\endgroup$
    – JayK23
    Jul 16, 2023 at 15:04
  • $\begingroup$ 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. $\endgroup$
    – Russel
    Jul 16, 2023 at 15:18
  • $\begingroup$ Understood! Thanks a lot! $\endgroup$
    – JayK23
    Jul 16, 2023 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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