Detect a Cycle in an Undirected Graph
easyGraphs II+10 XPTime limit 2s
A computer network has n machines and m two-way cables. Engineers want to know whether the cabling contains a loop: a path that leaves a machine and comes back to it without reusing any cable.
Input:
- line 1:
n m - next
mlines: a cableu v
Output: true if there is a cycle, otherwise false.
Constraints: 1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 10⁵, u ≠ v, no cable is listed twice. The network may be disconnected.
Think about it: add the cables one by one to a Union-Find: if a cable joins two machines that are already connected, it closes a cycle. (A DFS also works — a cycle shows up as a visited neighbour that is not your parent.)
Sample input 1
4 4 1 2 2 3 3 4 4 2
Sample output 1
true
Sample input 2
4 3 1 2 2 3 3 4
Sample output 2
false
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).