All problems

Loop-Free Pipe Systems

Medium · graph traversal

A village has n water tanks, numbered 0 to n - 1. Each entry of pipes is [a, b]: a pipe joining tank a and tank b, which water can flow along in both directions.

A system is a group of tanks that are joined together by pipes, directly or through other tanks, and that has no pipe to any tank outside the group. A tank with no pipes at all is a system on its own.

A system has a loop if you can start at one of its tanks, follow pipes without using any single pipe twice, and come back to the tank you started from. Pipes in a loop can be kept running in both directions around, so engineers like loops. The village inspector, however, wants to know how many systems have no loop.

Return the number of systems that have no loop.

Examples

Example 1

Input: n = 6, pipes = [[0, 1], [1, 2], [3, 4], [4, 5], [5, 3]]

Output: 1

Tanks 0, 1 and 2 form a line with no loop. Tanks 3, 4 and 5 form a triangle, which is a loop.

Example 2

Input: n = 4, pipes = []

Output: 4

Every tank is a system on its own, and none of them has a loop.

Example 3

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

Output: 0

All five tanks are in one system, and tanks 0, 1 and 2 make a loop.

Constraints