DWITE '09 R1 #5 - Running In Circles

View as PDF
Submit solution
Points: 7
Time limit: 1.0s
Memory limit: 64M
Problem type
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 \le N \le 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

Problem Resource: DWITE

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments


  • -1
    JinchengLuo2007  commented on March 9, 2024, 7:08 p.m.

    what if we get in a situation where there are 2 cycles?


    • 2
      d  commented on April 8, 2024, 3:41 a.m.

      if this happens, you should click on "Report an issue" and report the faulty test case


    • -1
      thunder200911133  commented on April 8, 2024, 1:03 a.m.

      I think output the longest one Idk, I am sorry if I am wrong