本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
说我们IIS7站长博客，有一篇博文用了他们的图片。
要求我们给他们一张图片6000元。要不然法院告我们
为避免不必要的麻烦，IIS7站长博客，全站内容图片下架、并积极应诉
博文内容全部不再显示，请需要相关资讯的站长朋友到必应搜索。谢谢！
另祝：版权碰瓷诈骗团伙，早日弃暗投明。
相关新闻：借版权之名、行诈骗之实，周某因犯诈骗罪被判处有期徒刑十一年六个月
叹！百花齐放的时代,渐行渐远!
这道题需要做一下模型转换，首先我们发现给定的边其实构成一个补图
如果我们暴力做这道题，那么就是遍历所有点，限制题目的边这样做收到了点的个数的制约
而我们可以这样想，我们把给点的边构图，那么其实就是求取他的补图的连通性
这里有一个好的发现就是，对于原来复杂度超时的代码来说，肯定是点数太多，才会超时，但是点数多意味着完全图的边数多，因为题目所给的边数最多只有20w
我们可以想到，其实答案中的连通块数目并不会特别多，因为肯定有相当一部分的点是在一个连通块中，如果我们能找到这个大的连通块，那么剩下就没几个点了
因此我们可以找到新图中的度最小的点，这里度最小，意味着补图中邻边越多，也就意味着找到这个点就能找到这个大连通块，我们发现，最小的点的度数最大就是n/m
因此我们一下就找到一个大小为n-n/m的连通块，对于剩下的点来说，即使暴力遍历，也是O(M)的算法
#include<bits/stdc++.h>
#define getsz(p) (p?p->sz:0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int N=4e5+10;
vector<int> num;
vector<int> g[N];
int in[N];
int st[N];
int vis[N];
int p[N],d[N];
int find(int x){
if(x!=p[x]){
p[x]=find(p[x]);
}
return p[x];
}
int main(){
ios::sync_with_stdio(false);
int n,m;
cin>>n>>m;
int i;
while(m--){
int a,b;
cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
in[a]++;
in[b]++;
}
int mx=0;
in[0]=0x3f3f3f3f;
for(i=1;i<=n;i++){
if(in[i]<in[mx]){
mx=i;
}
}
for(i=1;i<=n;i++){
p[i]=i;
d[i]=1;
}
for(i=0;i<(int)g[mx].size();i++){
vis[g[mx][i]]=1;
}
for(i=1;i<=n;i++){
if(!vis[i]){
p[i]=mx;
if(i!=mx)
d[mx]++;
}
}
for(i=1;i<=n;i++){
if(!vis[i])
continue;
memset(st,0,sizeof st);
for(int j=0;j<(int)g[i].size();j++){
st[g[i][j]]=1;
}
for(int j=1;j<=n;j++){
if(st[j]||j==i)
continue;
int pa=find(i);
int pb=find(j);
if(pa!=pb){
p[pa]=pb;
d[pb]+=d[pa];
}
}
}
for(i=1;i<=n;i++){
if(p[i]==i){
num.push_back(d[i]);
}
}
sort(num.begin(),num.end());
cout<<(int)num.size()<<endl;
for(auto x:num){
cout<<x<<" ";
}
cout<<endl;
return 0;
}
View Code
