1701. How Many Arrows Point At Each Vertex
A DIRECTED graph has n vertices numbered 1 to n and m arrows. Print the
IN-DEGREE of every vertex: how many arrows point at it.
4 vertices, arrows 1->2, 1->3, 2->4, 3->4 -> 0 1 1 2
Vertex 1 has nothing pointing at it, vertices 2 and 3 have one arrow each, and vertex 4 has two.
## The three things that have to be said
A graph problem is unanswerable without them, so this topic states all three every time.
directed? yes. An arrow u->v counts towards v and NOT towards u.
self-loops? allowed. u->u raises u's own in-degree by one.
parallel arrows? allowed. Three copies of 1->2 make vertex 2's in-degree 3.
disconnected? allowed. A vertex no arrow touches has in-degree 0.
Those are not decorations. A solution that adds 1 to both ends, or that deduplicates repeated arrows, or that only walks the part of the graph reachable from vertex 1, gets a different answer on the tests below.
## What most people try first
For each vertex, scan the whole arrow list and count the ones that end there.
It is obviously correct and it is O(n m), which at n = m = 2 * 10^5 is
4 * 10^10 comparisons.
## One pass is enough, because an arrow has one head
Nothing needs to be searched for. Each arrow contributes to exactly one in-degree, the one at its head, so reading the arrow and adding one to that counter is the whole algorithm:
deg = array of n zeros
for each arrow (u, v): deg[v] = deg[v] + 1
The reason it is correct is that the sum being computed is a sum over ARROWS, not over vertices. Reorganising a sum by what it is indexed over turns a nested loop into a single pass, and it is the reason every algorithm in this topic that needs in-degrees builds them this way.
## Why this is the first problem of the topic
Kahn's algorithm, which problems 1702, 1709 and 1713 all run, begins by building
exactly this array and then repeatedly removing a vertex whose in-degree has
reached 0. Problem 378 already counts how many vertices have in-degree 0;
printing all n of them is the array those algorithms actually need.
## Cost
Time O(n + m): one pass to clear the counters and one over the arrows. Space
O(n) for the counters, which is why no adjacency list is needed here at all.
An adjacency list would cost O(n + m) and an adjacency matrix O(n^2), and at
n = 2 * 10^5 the matrix is 4 * 10^10 entries and impossible. Nothing
overflows: an in-degree is at most m = 2 * 10^5.
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 line holding n integers separated by single spaces: for each vertex from 1 to n in order, how many arrows point at it. Print nothing else, and print no trailing words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.