All Tracks Algorithms Graphs Graph Representation Problem

Buggy Bot

Algorithms, Graph Representation, Graphs, Medium


Alice finally finished her CS assignment and programmed her robot to explore a directed graph G with n nodes (numbered 1 through n) and m edges.

Alice programmed the robot with a series of k instructions. The robot will attempt to execute one instruction per second in the given order; it won't repeat any instruction or return to an instruction it didn't execute. Each instruction is of the form "if the robot is currently at node x, it will move to node y". Note that if the robot is not currently at node x, it will ignore such an instruction. The robot is initially located at node 1.

Unfortunately, the robot is a bit buggy — at one moment in time, it can move from its current node to an arbitrary neighboring node (a node to which an edge leads from the current node). Note that this bug could have happened before any instructions, between any two instructions, or after all instructions; however, it couldn't have happened multiple times. It is also possible that this bug did not happen at all.

Alice is having trouble debugging the robot, and would like your help to determine all nodes where the robot could be located at the end.


  • \(1 \le n \le 100,000\)

  • \(1 \le m, k \le 1,000,000\)

  • \(1 \le a_i, b_i \le n\) for each valid i

  • \(1 \le x_i, y_i \le n\) for each valid i

  • each instruction for the robot will correspond to an existing directed edge

  • the graph won't contain loops — \(x_i \neq y_i\) for each valid i

  • the graph won't contain multiple edges — \((x_i,y_i) \neq (x_j,y_j)\) for each valid \(i \neq j\)

Input format:

The first line of the input contains three integers n, m and k, denoting the number of nodes, the number of edges and the number of instructions respectively.

Each of the following m lines contains two space-separated integers \(a_i\) and \(b_i\) denoting a directed edge from node \(a_i\) to node \(b_i\).

Each of the following k lines contains two space-separated integers \(x_i\) and \(y_i\) denoting an instruction for the robot.

Output format:

On the first line, print a single integer F — the number of possible final nodes for the robot.

On the second line, print F space-separated integers, representing the possible final nodes for the robot, in increasing order.

5 5 3
1 2
2 3
3 4
4 1
2 4
1 2
3 4
2 3
3 4

Some of the possible scenarios are the following (the starred arrows represent the robot moving because a bug occured):

1 -> 2 -> 3

1 -> 2 -*> 3 -> 4

There may be more scenarios where the robot took different paths; however, there is no way for the robot to end up in node 2 or back in node 1.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), TypeScript, Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

December Circuits '17

View All Notifications