1721. Where Nothing Comes In and Nothing Goes Out
n depots are joined by m one-way delivery routes. Squeeze the map as problem
1720 does: each group of mutually reachable depots becomes one point, and an
arrow joins two points when some route ran between those groups.
A point is a SOURCE when no arrow enters it and a SINK when no arrow leaves it. Print two integers: how many sources and how many sinks.
1->2, 2->3, 3->1, 3->4, 4->5 -> 1 1
1->2, 3->2 -> 2 1
1->2, 2->1 -> 1 1
4 depots, no routes -> 4 4
A single point with no arrows at all is both a source and a sink, which is why
the fourth example answers 4 4 rather than 4 0, and why the one-depot input
answers 1 1.
## Why this is the question worth asking about the squeezed map
Goods can be dropped into the network anywhere, but they can only ever reach a group from a group upstream of it. A source has nothing upstream, so SOMETHING must be dropped into every source or that group is never served, and the number of sources is the smallest number of drop points that reaches every depot. Symmetrically a sink is a group goods can never leave. Problem 1724 turns the two counts into the number of routes that would make the whole map one group.
## The three things that have to be said
directed? yes, and the two counts are the same question in opposite
directions, so one function answers both.
self-loops? allowed, and a self-loop is internal to its group, so it
makes a point neither a source nor a sink.
parallel arrows? allowed, and they do not change either count.
disconnected? allowed, and every piece contributes its own sources and
sinks, which is why the fourth example is 4 and 4.
## What most people try first
Counting vertices with in-degree 0 in the original graph, and calling those the
sources. That misses every source group of size two or more. On
1->2, 2->1, 1->3 no vertex at all has in-degree 0, because 1 and 2 point at
each other, yet the squeezed map has exactly one source. The groups have to be
computed first; there is no shortcut through degrees.
The second mistake is subtler. Having computed the groups, it is tempting to count a group as a source when none of ITS members has an incoming arrow. That is wrong for the same reason in reverse: members of a source group do have incoming arrows, from each other. Only arrows CROSSING between two different groups count.
## The method
comp[v] = group of v
hasIn[c] = true when some arrow (u, v) has comp[u] != comp[v] == c
hasOut[c] = true when some arrow (u, v) has c == comp[u] != comp[v]
sources = number of groups with hasIn false
sinks = number of groups with hasOut false
One pass over the arrows sets both arrays, and no deduplication is needed, because a boolean does not care how many arrows set it. That is the difference from problem 1720, which counts arrows and therefore must deduplicate.
## Cost
Time O(n + m), space O(n + m). The searches are iterative, 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. Both counts are at most
n = 200000, well inside a 32-bit integer.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - `u` may equal `v`, so self-loops can occur - the same route may be listed more than once - the map may be disconnected
Input
The first line contains two integers n and m, the number of depots and the number of one-way routes.
Each of the next m lines contains two integers u and v, a route FROM depot u TO depot v.
Output
Print two integers on one line separated by a single space: first how many points of the squeezed map have no arrow entering them, then how many have no arrow leaving them. A point with no arrows at all counts in both. Print nothing else.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.