369. Vertices With No Edges
Foundation1000 ms256 MBSolved by 0%
A vertex is isolated when no edge touches it. Print how many isolated vertices the graph has.
An isolated vertex is a component all by itself, which is why it is easy to miss: nothing in the edge list ever mentions it. A solution that walks the edges and never looks at the vertex range will report 0 every time.
This is the same degree array as problem 368, read differently.
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 isolated vertices.
Input6 3
1 2
3 4
4 5
Output1
Noteleaves vertex 6 unmentioned by any edge
Input3 0
Output3
Notehas no edges, so every vertex is isolated
Input4 3
1 2
2 3
3 4
Output0
Notetouches every vertex, so the answer is zero
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.