Skills101
← All coding problems

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 m lines: a cable u 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).

Loading editor…

Log in to run and submit your code — it's free.