Codeforces Round #599 (Div. 2) D. 0-1 MST

其实就是找连通块的数量。
注意set和vector这些容器不能边修改边遍历，需要在修改之前将迭代器往后加一。

//#pragma GCC optimize(3)
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=2e5+5;
const int mod=998244353;
int n,m;
map<int,int>mp[N];
bool vis[N];
set<int>ss;
void bfs(int s)
{
    queue<int>que;
    ss.erase(s);
    que.push(s);
    vis[s]=1;
    while(!que.empty())
    {
        int now=que.front();
        que.pop();
        set<int>::iterator it;
        for(it=ss.begin();it!=ss.end();)
        {
            int v=*it;
            ++it;
            if(!mp[now][v])
            {
                ss.erase(v);
                vis[v]=1;
                que.push(v);
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)ss.insert(i);
    //for(int i:ss)cout<<i<<endl;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        mp[u][v]=mp[v][u]=1;
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])bfs(i),ans++;
    }
    cout<<ans-1<<endl;
    return 0;
}

Codeforces Round #599 (Div. 2) D. 0-1 MST

原文：https://www.cnblogs.com/liuquanxu/p/11811448.html