394. Counting Paths of Two Edges
Count the paths of exactly two edges: sets of three vertices u, v, w
where u and w are both joined to v and u is not the same vertex as
w. Print how many there are, counting u - v - w and w - v - u as the
same path.
There is no traversal here and the answer is arithmetic. Fix the middle vertex
v: any two of its neighbours make one such path, and no two different choices
of neighbours give the same path. A vertex of degree d therefore contributes
d × (d - 1) / 2 paths, and the answer is that summed over every vertex.
The star test is the one to check your formula against: a centre of degree 4 gives 4 × 3 / 2 = 6, and the four leaves contribute nothing.
Degrees reach a hundred thousand, so d × (d - 1) / 2 is around five billion
for a single vertex. Use a 64-bit type.
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ m ≤ 200000` - There are no self-loops and no repeated edges.
Input
The first line contains two integers n and m, the number of vertices and
edges. Each of the next m lines contains two integers u and v, an
undirected edge between those vertices. Vertices are numbered 1 to n.
Output
Print one integer, the number of two-edge paths.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.