Loop in the Pipeline Network

EasyGraphs

Problem

A water utility has n junctions numbered 0 to n - 1 and a list of pipes; each [a, b] connects junctions a and b and water can flow either way.

Return true if the network contains a loop: a way to leave some junction and come back to it without using any pipe twice. Two separate pipes between the same pair of junctions form a loop, and so does a pipe from a junction to itself.

Example 1

Input:
n = 4, pipes = [[0, 1], [1, 2], [2, 0]]
Output:
true

0 → 1 → 2 → 0.

Example 2

Input:
n = 4, pipes = [[0, 1], [1, 2], [2, 3]]
Output:
false

A single line has no loop.

Example 3

Input:
n = 3, pipes = []
Output:
false

Constraints

  • 1 ≤ n ≤ 10^4
  • 0 ≤ pipes.length ≤ 2·10^4
  • 0 ≤ a, b < n

Hint

Show the first hint

Add pipes one at a time. When does a new pipe create a loop?

Walkthrough

How to approach it

01Clarify before coding

  • Is a pipe from a junction to itself a loop? Yes.
  • Do two parallel pipes count? Yes: go out on one, come back on the other.
  • Can the network be disconnected? Yes; a loop anywhere counts.

02Brute force

For every pipe, remove it and check with BFS whether its two ends are still connected; if so, that pipe lies on a loop.

Cost: O(m · (n + m)): about 6·10^8 steps at the limits.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.