All Tracks Algorithms Graphs Topological Sort Problem

Lonely Island
Tag(s):

Algorithms, Easy, Graph, Topological sorting

Problem
Editorial
Analytics

There are many islands that are connected by one-way bridges, that is, if a bridge connects islands \(a\) and \(b\), then you can only use the bridge to go from \(a\) to \(b\) but you cannot travel back by using the same. If you are on island \(a\), then you select (uniformly and randomly) one of the islands that are directly reachable from \(a\) through the one-way bridge and move to that island. You are stuck on an island if you cannot move any further. It is guaranteed that after leaving any island it is not possible to come back to that island.

Find the island that you are most likely to get stuck on. Two islands are considered equally likely if the absolute difference of the probabilities of ending up on them is \(<=10^{-9}\).

Input format

  • First line: Three integers \(n\) (the number of islands), \(m\) (the number of one-way bridges), and \(r\) (the index of the island you are initially on)
  • Next \(m\) lines: Two integers \(u_i\) and \(v_i\) representing a one-way bridge from island \(u_i\) to \(v_i\).

Output format

Print the index of the island that you are most likely to get stuck on. If there are multiple islands,then print them in the increasing order of indices (space separated values in a single line).

Input Constraints

\(1 \le n \le 200000\\ 1 \le m \le 500000\\1 \le u_i,v_i,r \le n\)

 

SAMPLE INPUT
5 7 1
1 2
1 3
1 4
1 5
2 4
2 5
3 4
SAMPLE OUTPUT
4 
Explanation

There are two islands on which you could get stuck- 4 and 5 with 4 being more probable.

Time Limit: 1.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), 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, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

November Easy' 18

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?