One-Way Districts
Medium · graph traversal
A town has n junctions, numbered 0 to n - 1, joined by one-way streets. Each entry of streets is [a, b]: you may drive from junction a to junction b, but not back along that street.
Two junctions belong to the same district if you can drive from each of them to the other, passing through any other junctions on the way. Every junction belongs to exactly one district, and a junction that cannot be part of any loop is a district on its own.
Return the number of districts in the town.
The same street may appear more than once in the list, and no street starts and ends at the same junction.
Examples
Example 1
Input: n = 7, streets = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 5], [5, 3], [6, 5]]
Output: 3
Junctions 0, 1 and 2 form a loop, and so do 3, 4 and 5. You can drive from the first loop to the second but never back. Junction 6 only has a street leaving it, so it is a district alone.
Example 2
Input: n = 4, streets = [[0, 1], [1, 2], [2, 3]]
Output: 4
Every street can only be used in one direction, so no two junctions can reach each other.
Constraints
- 1 <= n <= 10^5
- 0 <= len(streets) <= 2 * 10^5
- streets[i] = [a, b] with 0 <= a, b < n and a != b