【寒假坚持学习鸭】2.2日（dfs求连通块）

题目地址
题意：给你一个有m条权值为1的无向边的完全图，问你得到的最小生成树的权值为多少
tag:最小生成树，贪心思想
题解：能用权值为0的边就用。
那么对那m条边的端点，将能用0边到达的点都缩在一起
形成一个个连通块
在对缩完的点进行用1边连接，所以答案为缩完后的点数减一

dfs求连通块
u[x] ：与vis[x]一样的作用
set g[maxn] 每个点都记录自己与哪些点距离为1
set vis 每个点通过g[maxn]结合着vis便可知自己还与哪些点距离为0
vector ret 对dfs中的的点暂时记录与其距离为0的点

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100005;
set<int>g[maxn];
set<int>vis;
int u[maxn];
void dfs(int x){
   
    u[x]=1;
    vis.erase(x);
    vector<int>ret;
    for(set<int>::iterator it = vis.begin(); it != vis.end(); ++it){
   
        if(!g[x].count(*it)){
   
            ret.push_back(*it);
        }
    }
    for(vector<int>::iterator t = ret.begin(); t != ret.end(); ++t ){
   
        vis.erase(*t);
    }
    for(vector<int>::iterator t = ret.begin(); t != ret.end(); ++t){
   
        u[*t]=1;
        dfs(*t);
    }
    return;
}
int main(){
   
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
   
        int x,y;
        cin>>x>>y;
        g[x].insert(y);
        g[y].insert(x);
    }
    for(int i=1;i<=n;i++){
   
        vis.insert(i);
    }
    int ans = 0;
    for(int i=1;i<=n;i++){
   
        if(!u[i]){
   
            ans++;
            dfs(i);
        }
    }
    cout<<ans-1<<endl;
}