1717. How Many Mutually Reachable Groups
A DIRECTED graph has n vertices and m arrows. Two vertices belong to the
same GROUP when each can reach the other by following arrows forwards. Print how
many groups there are.
1->2, 2->3, 3->1, 3->4, 4->5 -> 3 {1,2,3} {4} {5}
3->1, 1->2, 2->3 -> 1
1->2, 2->3, 3->4 -> 4 no cycle, so four groups of one
4 vertices, no arrows -> 4
Every vertex is in exactly one group, so the answer is between 1 and n. These
groups are the STRONGLY CONNECTED COMPONENTS, and counting them is the question
that makes the condensation of problems 1720 to 1724 possible at all.
## The three things that have to be said
directed? yes, and reversing one arrow can change the count.
self-loops? allowed. u -> u leaves u in a group of one.
parallel arrows? allowed, and a second copy never merges two groups.
disconnected? allowed. Each piece contributes its own groups.
## What most people try first
Counting the connected pieces while ignoring the arrow directions, which is what
problem 363 does. That is wrong, and 1->2, 2->3, 3->4 is the counterexample:
one undirected piece, four groups. Direction cannot be thrown away.
The next attempt is problem 1714's two searches from every vertex, which is
correct at O(n(n + m)) and far too slow at n = m = 200000.
## Kosaraju, two passes for all the groups at once
pass one depth-first search the graph as given and append each vertex to a
list when it FINISHES, after everything below it is done
pass two search the REVERSED graph, taking starting vertices in REVERSE
finishing order; each search that starts fresh collects one group
The answer is the number of searches pass two had to start.
## Why that is right, in one paragraph
Contract each group to a single point. The result cannot contain a cycle, because a cycle through two groups would make all their vertices mutually reachable and so one group. So the groups sit in an order. The last vertex to finish in pass one lies in a group that nothing outside points INTO, and a reversed search from it therefore cannot escape its own group while reaching all of it. Remove that group and the next unvisited vertex in reverse finishing order has the same property for the remainder. So each pass-two search collects exactly one group and the count is right.
## Cost
Time O(n + m), space O(n + m) for the two adjacency lists. Both passes use
an explicit stack, since a path of 200000 vertices is permitted and recursion on
it overflows Python's recursion limit and the default stack in C, C++ and Java.
The count fits in a 32-bit integer easily, since it never exceeds
n = 200000.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - `u` may equal `v`, so self-loops can occur - the same arrow may be listed more than once - the graph may be disconnected
Input
The first line contains two integers n and m, the number of vertices and the number of arrows.
Each of the next m lines contains two integers u and v, an arrow FROM u TO v.
Output
Print one integer on its own line: how many groups of mutually reachable vertices the graph splits into. The answer is between 1 and n. Print no other text.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.