【乱搞】Codeforces EDU37 Connected Components

题目大意:

给出n个点构成的完全图，删去其中m条边，求剩下的联通块数量，以及每个联通块的大小

分析：

根据n的数据范围，分段函数：
若n小于2000，直接暴力算，复杂度$O(n^2)$
否则，我们这样考虑：
将给出的删边看作一条边，这样一来，对于任意一点，与其没有连边的点必然与它属于同一个联通块（即在原图中有边相连）。
利用贪心的思想，我们试图找到一个度数最小的点，以使得我们能够确定的这个联通块尽量大。
很容易发现，在所有删边情况中，所有点度数最小值的最大情况为所有的删边均匀分布：即度数最小的点的度数最大值为$\frac {2m} n$。
在这$\frac {2m} n$个点中，我们对每个点用O(n)的复杂度，求得其是否与我们选中的点（即度数最小的点）属于同一个联通块，总复杂度为$O(\frac {2m} n *n)=O(2m)$。
现在，我们相当于把问题转化为在$\frac {2m} n$个点中找联通块，不难发现，因为$n＞2000,m<200000,$所以$\frac {2m} n＜200$
即：我们在200个点中找联通块，所以最终$O((\frac {2m} n)^2)$暴力计算即可。
（其实后来发现，根本没必要分n<2000的情况，因为$m<\frac {n*(n-1)} 2$，直接用后面的方法，依旧可以通过）
代码写得有点丑：

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstring>
#define SF scanf
#define PF printf
#define MAXN 200010
using namespace std;
int n,m,szx;
vector<int> a[MAXN],re;
bool flag[MAXN],vis[MAXN];
int fa[MAXN],sz[MAXN];
void dfs(int x,int tag){sz[tag]++;vis[x]=1;sort(a[x].begin(),a[x].end());int j=0;for(int i=0;j<re.size()&&i<a[x].size();i++){for(;j<re.size()&&re[j]<a[x][i];j++)if(vis[re[j]]==0&&flag[re[j]]==1)dfs(re[j],tag);if(j<re.size()&&re[j]==a[x][i])j++;}for(;j<re.size();j++)if(vis[re[j]]==0)dfs(re[j],tag);
}
bool check(int x){sort(a[x].begin(),a[x].end());int j=1;vis[x]=1;for(int i=0;j<=n&&i<a[x].size();i++){for(;j<a[x][i];j++){if(vis[j]==1)continue;if(flag[j]==0)return 1;   if(check(j))return 1;}if(j==a[x][i])j++;}for(;j<=n;j++){if(vis[j]==1)continue;if(flag[j]==0)return 1;   if(check(j))return 1;}return 0;
}
void change(int x){sort(a[x].begin(),a[x].end());flag[x]=0;int j=1;for(int i=0;j<=n&&i<a[x].size();i++){for(;j<a[x][i];j++)if(flag[j]==1)change(j);if(j==a[x][i])j++;}for(;j<=n;j++)if(flag[j]==1)change(j);  
}
int main(){SF("%d%d",&n,&m);int u,v;for(int i=1;i<=m;i++){SF("%d%d",&u,&v);a[u].push_back(v);a[v].push_back(u);}if(n<=2000){int cnt=0;for(int i=1;i<=n;i++){re.push_back(i);flag[i]=1;}for(int i=1;i<=n;i++)if(vis[i]==0)dfs(i,++cnt);PF("%d\n",cnt);sort(sz+1,sz+1+cnt);for(int i=1;i<=cnt;i++)PF("%d ",sz[i]);return 0;}int id=1;for(int i=1;i<=n;i++)if(a[id].size()>a[i].size())id=i;for(int i=0;i<a[id].size();i++)flag[a[id][i]]=1;   for(int i=1;i<=n;i++)if(flag[i]==1&&vis[i]==0&&check(i))change(i);memset(vis,0,sizeof vis);for(int i=1;i<=n;i++){if(flag[i]==0)szx++;else{re.push_back(i);}}int cnt=0;for(int i=0;i<re.size();i++)if(vis[re[i]]==0)dfs(re[i],++cnt);sort(sz+1,sz+1+cnt);PF("%d\n",cnt+1);for(int i=1;i<=cnt;i++)PF("%d ",sz[i]);PF("%d",szx);
}