T27351:01最小生成树

mst, http://cs101.openjudge.cn/practice/27351/

思路：优先选权值为 0 的边，再用权值为 1 的边补全连通性

#include <iostream>
#include <vector>
#include <unordered_set>
#include <queue>
using namespace std;

const int MAX_N = 200005;
unordered_set<int> adj[MAX_N];  
unordered_set<int> unvisited; 
queue<int> q;             

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        unvisited.insert(i);
    }
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        adj[a].insert(b);
        adj[b].insert(a);
    }
    int component_count = 0;
    for (int i = 1; i <= n; ++i) {
        if (unvisited.count(i)) { 
            component_count++;
            q.push(i);
            unvisited.erase(i); 
            while (!q.empty()) {
                int u = q.front();
                q.pop();
                vector<int> neighbors;
                for (auto it = unvisited.begin(); it != unvisited.end();) {
                    int v = *it;
                    if (adj[u].count(v) == 0) {
                        neighbors.push_back(v);
                        it = unvisited.erase(it);  
                    } else {
                        it++;
                    }
                }
                for (int v : neighbors) {
                    q.push(v);
                }
            }
        }
    }
    cout << component_count - 1 << endl;

    return 0;
}