HCI '16 - Redstone Repeaters

View as PDF
Submit solution
Points: 10 (partial)
Time limit: 0.6s
Memory limit: 256M
Authors:
zj97, damian, fanpu
Problem type

Bcy is playing Minecraft 1.10 and he is building a complicated circuit using redstone dust and repeaters and comparators and redstone blocks and all that good stuff to spice up his already high-tech virtual home. Yay. However, as any redstone Minecrafter would know, if bcy places 2 repeaters facing opposite directions, hooks them up with redstone wire and sends a redstone current through the circuit, it would result in an infinite loop and a 'forever-on' status!!!! Oh no!!!

Infinite Loop

bcy's circuit has suddenly messed up. He believes it is caused by an infinite repeater loop in his circuit that he must have accidentally triggered at some point in his redstone engineering. With all the pistons and intricate wiring in the way, bcy cannot solve the problem on his own. Being a C++ freak, you decided to help bcy out by coding a program to test if any infinite loops were present.

Input Specification

The first line of input contains 2 integers, N and E, space-separated. N represents the number of redstone repeaters (conveniently labelled 1 \dots N) in bcy's circuit, while E represents the number of redstone wires hooked up to each repeater (can be related to the edges of a graph). The following E lines of input contain 2 integers, A and B. These define a connection between repeater A and repeater B. It is guaranteed that this defines a 1-directional connection where A points to B but not otherwise.

Output Specification

Output, on a single line, Infinite Loop Present if only 1 infinite loop is present.

Output Infinite Loops Present if more than 1 infinite loop is present. If there are no infinite loops, output No Infinite Loops.

Constraints

Subtask 1 [100%]

1 \le N \le 1000

1 \le E \le 1100

Subtask 2 [0%]

Sample test cases.

Sample Input 1

4 4
1 2
2 4
1 3
4 4

Sample Output 1

Infinite Loop Present

Explanation 1

According to the last line of input where repeater 4 is connected to itself. This means that an infinite loop is present as the redstone current would come out of repeater 4 and go back into itself. The graph can be visualized as follows:

As such, an infinite loop is present.

Sample Input 2

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

Sample Output 2

Infinite Loops Present

Explanation 2

The inputs 1 2, 2 3, and 3 1 all create a triangle like loop. And the input 4 4 means repeater 4 is connected to itself. Thus there are 2 infinite loops and we output Infinite Loops Present. The graph can be visualized as follows:

Comments


  • 1
    Vastaway  commented on March 5, 2024, 5:18 p.m.

    Clarification: For those like me who aren't experienced in graphs and cycles, the problem is asking for the amount of Simple Cycles in the graph. A simple cycle is any path in a graph that has the same start and end node. This is seen in 4 -> 4 and 1 -> 2 -> 3 -> 1 in the second example. They are asking for the amount of unique simple cycles. Good luck and have fun!


  • -1
    gavin_chen  commented on Nov. 10, 2022, 1:42 a.m.

    jusr realized the image isnt correct...


  • -2
    Ninjaclasher  commented on June 14, 2017, 11:05 p.m. ← edited

    Does anyone knows what RTE (aborted) means? It happens when I run this line of code: ss.pop_front();in the line while (ss.front() != pos) ss.pop_front();


    • 0
      Kirito  commented on June 15, 2017, 4:53 a.m. ← edited

      If ss is empty, the program will abort.

      while (!ss.empty() && ss.front() != pos) ss.pop_front();

      Will probably fix the problem.


  • 0
    Ninjaclasher  commented on June 3, 2017, 9:21 p.m. ← edit 2

    If there was for example a case: 4 5 1 2 3 1 2 3 3 4 4 2

    Would that be considered 2 loops or 3 loops?