Daily Archives: 6 October 2017

Good evening master Wayne.

Joker and his gang attended Black Hat USA 2017 where they learned of a new way on how to damage our city!
Specifically, tomorrow night they will try to damage the water pumps of Gotham using bubbles!
The bubbles cause corrosion to the pumps and in a few hours they will damage them with catastrophic results!
To dash Joker’s plan, besides stopping him, you need to make sure that the city network does not contain loops.
If Joker manages to inject bubbles to the network and they enter a loop, they will still cause damage to that area even though you would have already arrested Joker and his gang.

Given the map of the water distribution system, you need to make sure that the map does not contain loops.

Input data

On the first line there will be an integer T, the number of test cases to follow.
For each test case, there will be 2 input lines:

1. On the first line of the test case, there will be 2 integers V and E, where V is the number of vertices and E is the number of edges.
2. On the second line, there will be E pairs of integers separated by a space character. Each pair shows a two way connection between vector A with vector B.

Output data

For each test case you will have to write one line that contains an integer, in the case where there is a loop you will write the number 1 or else you will write the number 0.

Limitations and notes

1 ≤ T ≤ 1000
1 ≤ V ≤ 1000
1 ≤ E ≤ 10000
0 ≤ A,B ≤ V-1

Vangelis the bear is Batman! (or Batbear to be more precise).

Reading material

• https://en.wikipedia.org/wiki/Cycle_(graph_theory)
• https://en.wikipedia.org/wiki/Cycle_detection
• https://www.blackhat.com/us-17/briefings/schedule/#evil-bubbles-or-how-to-deliver-attack-payload-via-the-physics-of-the-process-7689

Supplementary material

• Random test case generator – [download id=”3801″]