10/31/2019 Crossing Khazad-dum 1 | basic-algorithms-fall-2019-pa4 Question | Contests | HackerRank
PRACTICE COMPETE JOBS LEADERBOARD Search Sf3126 All Contests basic-algorithms-fall-2019-pa4 Crossing Khazad-dum 1
Crossing Khazad-dum 1 by shoup
Problem Submissions Leaderboard
The fellowship has decided upon crossing Moria for the paths in the mountains are occupied by wargs. Unfortunately Gandalf is having a hard time remembering the paths inside the great caves as it has been a long time since he has passed through here.
The fellowship is currently being pursued by hordes of orcs and needs to escape as fast as possible from the dungeons. Gandalf has given you the all important task of identifying the perils ahead. As there are too many orcs pursuing the fellowship, if you return to any room where you have previously been, it will be filled with orcs. Gandalf wants you to identify if there is a path which will lead to your doom (by making you visit some room where you already walked through) so that he may take measures to avoid it (assume the passages are one way for simplicity).
Input Format
The map of Moria is presented as a series of passages which connect two rooms in the great labyrinth.
The first line has the number of rooms and number of passages in the kingdom. The next lines have two numbers
which tell that there is a passage from to .
Constraints
Output Format
If there is no loop, output 0 on a line by itself.
If there is a loop, output 1 on a line by itself, and then, on the following line, output the rooms appearing in one such loop, as follows. If the loop is x1 -> x2 -> -> xK -> x1, where xi -> xj means there is a passage from xi to xj, then output x1 x2 xK, with a single space between each room number. If there are several loops, it doesnt matter which one you print out. It also doesnt matter which room in the loop you start with, but the ordering should respect the passages in the loop. For example, if you output 17 6 8, there should passages from 17 to 6, from 6 to 8, and from 8 to 17.
Sample Input 0
44 12 23 34 41
Sample Output 0
https://www.hackerrank.com/contests/basic-algorithms-fall-2019-pa4/challenges/crossing-khazad-dum-1 1/3
10/31/2019
Crossing Khazad-dum 1 | basic-algorithms-fall-2019-pa4 Question | Contests | HackerRank
1 1234
Sample Input 1
55 12 23 34 45 51
Sample Output 1
1 12345
Sample Input 2
32 12 23
Sample Output 2
0
Current Buffer (saved locally, editable)
Java 8
1 2 3 4 5 6 7
importjava.io.*; importjava.util.*;
publicclassSolution{
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should
be named Solution. */
8} 9}
https://www.hackerrank.com/contests/basic-algorithms-fall-2019-pa4/challenges/crossing-khazad-dum-1
2/3
Contest ends in 11 days
Submissions: 9 Max Score: 100 Difficulty: Medium
Rate This Challenge:
More
Line: 1 Col: 1
10/31/2019 Crossing Khazad-dum 1 | basic-algorithms-fall-2019-pa4 Question | Contests | HackerRank
Upload Code as File Test against custom input
Run Code
Submit Code
Contest Calendar | Interview Prep | Blog | Scoring | Environment | FAQ | About Us | Support | Careers | Terms Of Service | Privacy Policy | Request a Feature
https://www.hackerrank.com/contests/basic-algorithms-fall-2019-pa4/challenges/crossing-khazad-dum-1 3/3
Reviews
There are no reviews yet.