371. Exactly K Steps Away
Count how many vertices sit exactly k edges away from vertex s.
Breadth-first search from s labels every reachable vertex with its distance,
as in problem 364. The answer is how many of those labels equal k.
Two cases decide whether this is right. Vertex s itself is at distance 0, so
when k is 0 the answer is 1. And unreachable vertices have no distance at
all; they must not be counted, whatever k is.
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ m ≤ 200000` - `1 ≤ s ≤ n` - `0 ≤ k ≤ 100000`
Input
The first line contains four integers n, m, s and k: the number of
vertices, the number of edges, the vertex to start from and the distance to
count. Each of the next m lines contains two integers u and v, an
undirected edge. Vertices are numbered 1 to n.
Output
Print one integer, the number of vertices at distance exactly k.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.