CF1900分，感觉是个不错的题

题意：给你n个点，m条边，每条边上u,v距离为1，未标注距离的边距离全部为0，求最小生成树(即求0的连通块数量-1)

解法1(dfs+set)：

这个方法比第2个方法简单很多,利用了set容器可以去除其容器内部元素的特性。此时的set<int> s就充当了有几个数未被处理过。我每一次开始新的dfs遍历的时候，都会构造出新的一组连通块(即当前最大化了其内部0连通块的可能性)。

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn=1e5+5;
set<int>s,v[maxn];
int n,m;
void dfs(int x){
    vector<int> vec;
    for(auto i:s){
        if(v[x].find(i)==v[x].end()){
            vec.push_back(i);
        }
    }
    for(auto i:vec) s.erase(i);
    for(auto i:vec) dfs(i);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;cin>>x>>y;
        v[x].insert(y);
        v[y].insert(x);
    }
    int ans=0;
    for(int i=1;i<=n;i++) s.insert(i);
    for(int i=1;i<=n;i++){
        if(s.find(i)!=s.end()){
            ans+=1;
            dfs(i);
        }
    }
    cout<<ans-1<<endl;
}

View Code

解法2(dsu)：

遍历1~n，比如到了第i个点，我们对[1,i）这些数字处理，通过mp来覆盖，如果说对于该集合的size>该集合被覆盖的mp数量，那么说明肯定有0边相连，那么这2个集合即可构成一个新的联通集合。

所以我们最后判定有几个连通块的时候，就是看fa[i]==i的数量有几个。

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define mem(a,b) memset(a,b,sizeof(a))
#define IO ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
const int INF=0x3f3f3f3f;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
const int maxn=1e5+5;
int tot,head[maxn];
struct E{
    int to,next;
}edge[maxn<<1];
void add(int u,int v){
    edge[tot].to=v;
    edge[tot].next=head[u];
    head[u]=tot++;
}
int fa[maxn],n,m;
map<int,int> mp;
int sz[maxn];
int find(int x){
    while(x!=fa[x]) x=fa[x]=fa[fa[x]];
    return x;
}
void merge(int u,int v){
    int eu=find(u),ev=find(v);
    if(eu==ev) return ;
    fa[ev]=eu;
}
int main(){
    cin>>n>>m;mem(head,-1);
    for(int i=0;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        add(u,v);add(v,u);
    }
    vector<int> g;
    for(int i=1;i<=n;i++){
        sz[i]=1;mp.clear();
        for(int j=head[i];j!=-1;j=edge[j].next){
            int v=edge[j].to;
            if(v>=i) continue;
            int ev=find(v);
            mp[ev]++;            
        }
        for(int j=0;j<g.size();j++){
            int s=find(g[j]);int t=find(i);
            if(s==t) continue;
            if(sz[s]>mp[s]){
                int ei=find(i),es=find(s);
                fa[ei]=es; 
                sz[es]+=sz[ei];    
            }
        }
        int fx=find(i);
        if(fx==i) g.push_back(fx);
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(fa[i]==i) cnt++;
    }
    cout<<cnt-1<<endl;
}

View Code