• CF1242B 0-1 MST

1.CF1242B 0-1 MST

求补图中联通块个数

先找到原图中度数最小的点，该点在补图中度数最大，标记原图中与其相连的所有点，补图中所有的点都与其相连

暴力遍历每个点，若已经与度最小的点相连或者为该点则跳过，标记与该点相连的所有点，与未标记的所有点相连

边数最多只有 1 0 5 10^5 105条，复杂度并不会很大

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int maxn=2e5+5,inf=0x3f3f3f3f;
int n,m,k,t,cnt,tt;
int f[maxn],vis[maxn],v[maxn],size[maxn],du[maxn];
vector<int>e[maxn];
inline void add(int u,int v){
	e[u].push_back(v);
}
int find(int x){
	if(f[x]==x)return x;
	else return f[x]=find(f[x]);
}
inline void hb(int x,int y){
	f[find(x)]=find(y);
}
set<pair<int,int>>st;
signed main(){
	cin>>n>>m;
	int mm=inf;
	int id;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);
		add(v,u);
		du[u]++,du[v]++;
	}
	for(int i=1;i<=n;i++){
		if(du[i]<mm){
			mm=du[i];
			id=i;
		}
		f[i]=i;
	}
	for(auto x:e[id]){
		vis[x]=1;
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			hb(i,id);
		}
	}
	int tim=1;
	for(int i=1;i<=n;i++){
		if(!vis[i]||i==id)continue;
		tim++;
		memset(v,0,sizeof v);
		for(auto x:e[i]){
			v[x]=1;
		}
		for(int j=1;j<=n;j++){
			if(!v[j]){
				hb(i,j);
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(f[i]==i){
			cnt++;
		}
		size[find(i)]++;
	}
	for(int i=1;i<=n;i++){
		if(f[i]==i){
			st.insert({size[i],i});
		}
	}
	cout<<cnt-1<<endl;
	/*for(auto x:st){
		cout<<x.first<<" ";
	}*/
	return 0;
}