DWITE '09 R1 #5 - Running In Circles

View as PDF

Submit solution

Points: 6
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
DWITE Online Computer Programming Contest, October 2009, Problem 5

Given a directional graph (think of it as a map of one way streets), cycles (a loop) are often involved in various problems. We know that one (and only one) cycle exists, and we want to find its length.

The input will contain 5 sets of input. The first line will contain a single integer, 1 \leq N \leq 100, number of pairs describing the graph. Followed by N lines, each having two integers separated by a space. Each of the integers refers to a node, with a directional path from first to second. Node IDs are between 1 and 100, inclusive. The first node in the list is guaranteed to have a path to the cycle.

For example: If the graph is described by 4 pairs: (1, 2), (2, 3), (3, 1), (4, 5); Then it describes a disjoint graph — a cycle of length 3 and another pair of nodes. Since it's guaranteed that starting at Node 1 will lead to a cycle, it shouldn't matter that it's not connected to 4 or 5.

Note: a node could link to itself (1 \to 1) and that will form a cycle of size 1.

The output will contain 5 lines, each an integer size of the cycle found in a graph.

Sample Input

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

Sample Output

1
2
3
3
3

Attribution-NonCommercial-ShareAlike 3.0 Unported (CC BY-NC-SA 3.0) Problem Resource: DWITE


Comments

There are no comments at the moment.