0-1 MST
Contest: Codeforces Round 599 (Div. 1)
Difficulty rating: 1900
Tags: dfs and similar, dsu, graphs, sortings

Ujan has a lot of useless stuff in his drawers, a considerable part of which are his math notebooks: it is time to sort them out. This time he found an old dusty graph theory notebook with a description of a graph.

It is an undirected weighted graph on $$$n$$$ vertices. It is a complete graph: each pair of vertices is connected by an edge. The weight of each edge is either $$$0$$$ or $$$1$$$; exactly $$$m$$$ edges have weight $$$1$$$, and all others have weight $$$0$$$.

Since Ujan doesn't really want to organize his notes, he decided to find the weight of the minimum spanning tree of the graph. (The weight of a spanning tree is the sum of all its edges.) Can you find the answer for Ujan so he stops procrastinating?

Input format:
The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10^5$$$, $$$0 \leq m \leq \min(\frac{n(n-1)}{2},10^5)$$$), the number of vertices and the number of edges of weight $$$1$$$ in the graph.

The $$$i$$$-th of the next $$$m$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$, $$$a_i \neq b_i$$$), the endpoints of the $$$i$$$-th edge of weight $$$1$$$.

It is guaranteed that no edge appears twice in the input.

Output format:
Output a single integer, the weight of the minimum spanning tree of the graph.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
The graph from the first sample is shown below. Dashed edges have weight $$$0$$$, other edges have weight $$$1$$$. One of the minimum spanning trees is highlighted in orange and has total weight $$$2$$$.

In the second sample, all edges have weight $$$0$$$ so any spanning tree has total weight $$$0$$$.

Example input:
6 11
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6

Example output:
2

Example input:
3 0

Example output:
0

Editorial:
First examine the given graph where there are only edges of weight $$$0$$$: suppose that the number of connected components in this subgraph is $$$k$$$. Then the minimum spanning tree of the given graph is equal to $$$k-1$$$. Therefore, we need to find the number of such (zero weight) components in the given graph.
The following is a $$$O(m + n \log n)$$$ solution. Let's maintain the zero weight components in the disjoint set union, and let's also store the size of each such component. Then we iterate over all vertices $$$v$$$ from $$$1$$$ to $$$n$$$. Put the vertex $$$v$$$ in a new component of size $$$1$$$. Then we iterate over the weight $$$1$$$ edges $$$\{u, v\}$$$ such that $$$u < v$$$. For each of the zero weight components, we count the number of edges from this component to $$$v$$$. If the number of such edges is less than the size of the component of $$$u$$$, we should merge the component of $$$u$$$ with $$$v$$$ (because there is at least one $$$0$$$ weight edge between this component and $$$v$$$). Otherwise we should not merge the component with $$$v$$$. In the end, we get the number of zero weight components.
What is the complexity of such algorithm? In total, $$$n$$$ new components are created in the course of the algorithm (a new one for each of the $$$n$$$ vertices). When we merge some old component with $$$v$$$, the number of components decreases by $$$1$$$. Thus the total number of such cases during the algorithm is at most $$$O(n)$$$, and for each we have one merge call for DSU. This part has $$$O(n \log n)$$$ complexity.
When we don't merge an old component with $$$v$$$, there is at least one edge of weight $$$1$$$ from this component to $$$v$$$. Therefore, the total number of such cases is at most the number of edges, $$$m$$$. Thus the complexity of processing these cases is $$$O(m)$$$.
Hence, the total complexity of the algorithm is $$$O(n \log n + m)$$$.