385. Edges Inside One Component
Print how many edges lie inside the component that contains vertex 1.
Problem 367 measured a component by counting its vertices. This counts its edges, and the two are not interchangeable: a component with 3 vertices has 2 edges if it is a path and 3 if it is a triangle.
The tidy way is two steps. Mark everything reachable from vertex 1, then count the edges whose endpoints are marked. Since an edge cannot cross between components, checking one endpoint is enough.
Trying instead to count edges as you traverse is where this goes wrong. Every edge is offered twice, once from each end, so a naive count doubles it.
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 edges in vertex 1's component.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.