题意：
现有一个(n,nleq 10^5)个结点的完全图。
给出(m,mleq 10^5)条(1)边，其余边全是(0)边。
现在要求这个图的(MST)权值为多少。
思路：
- 显然有一个暴力的思路：用一个队列维护已经在(MST)中的结点，那么我们直接枚举所有的(0)边进行判断然后入队即可。最终求出了(x)个连通块，那么答案即为(x-1)。
- 但在这里(0)边的数量过多我们无法进行枚举。注意到暴力的做法中我们是“添加”边，我们可以倒过来考虑，即“删除”边：我们枚举每条(1)边并且保留这些结点，将其余所有的结点直接加入队中。
- 这里我们用一个(set)来维护剩下未加入的点，这样可以方便从中删除结点。
- 一个点会出入(set)和队列至多一次，一条边只有两个点，也就是一个点最多会保留在(set)里面两次。所以总的复杂度为(O(nlogn))。
我的代码中为了图方便直接用的邻接矩阵，用map来存，所以复杂度多了个(log)。
代码如下：
/*
* Author: heyuhhh
* Created Time: 2020/3/5 16:55:05
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '
'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5;
int n, m;
map <int, bool> mp[N];
set <int> s;
queue <int> q;
void run() {
cin >> n >> m;
for(int i = 1; i <= m; i++) {
int u, v; cin >> u >> v;
mp[u][v] = mp[v][u] = true;
}
for(int i = 1; i <= n; i++) s.insert(i);
int t = 0;
while(!s.empty()) {
auto tmp = s.begin();
q.push(*tmp);
s.erase(tmp);
++t;
while(!q.empty()) {
int u = q.front(); q.pop();
for(auto it = s.begin(), nxt = it; it != s.end(); it = nxt) {
int v = *it;
++nxt;
if(mp[u].find(v) == mp[u].end()) {
q.push(v);
s.erase(it);
}
}
}
}
cout << t - 1 << '
';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
run();
return 0;
}