没有数据结构就很棒
一个看上去非常玄学的代码
const int N=1e5+10,M=2e6+10; int n,m; int fa[N]; int Find(int x){ return fa[x]==x?x:fa[x]=Find(fa[x]); } vector <int> G[N]; typedef vector <int> ::iterator iter; void merge(int x,int y){ x=Find(x),y=Find(y); if(x==y) return; vector <int> tmp;tmp.clear(); if(G[x].size()>G[y].size()) swap(x,y); int p=0; for(reg int i=0;i<(int)G[x].size();i++){ while(p<(int)G[y].size()&&G[y][p]<G[x][i]) p++; if(p>=(int)G[y].size()||G[y][p]!=G[x][i]) { tmp.push_back(G[x][i]); G[x].erase(G[x].begin()+i); i--; } } fa[y]=x; rep(i,0,tmp.size()-1) merge(x,tmp[i]); } int cnt[N]; int ans[N],ac; bool go[N]; void Sort(vector <int> &V){ if(V.size()<20000) return sort(V.begin(),V.end()); memset(go,0,sizeof go); rep(i,0,V.size()) go[V[i]]=true; V.clear(); rep(i,1,n) if(go[i]) V.push_back(i); } int num[N]; bool cmp(int x,int y){ return G[x].size()<G[y].size(); } int main(){ n=rd(),m=rd(); rep(i,1,n) fa[i]=num[i]=i; rep(i,1,m) { int u=rd(),v=rd(); G[u].push_back(v); G[v].push_back(u); } rep(i,1,n) Sort(G[i]); sort(num+1,num+n+1,cmp); rep(i,1,n) if(Find(num[i])==num[i]) { memset(go,0,sizeof go); rep(j,0,G[num[i]].size()-1) go[G[num[i]][j]]=1; rep(j,1,n) if(num[i]!=j&&!go[j]) merge(num[i],j); } rep(i,1,n) cnt[Find(i)]++; rep(i,1,n) if(cnt[i]) ans[++ac]=cnt[i]; sort(ans+1,ans+ac+1); printf("%d\n",ac); rep(i,1,ac) printf("%d",ans[i]),putchar(i==ac?'\n':' '); }我这个代码大概是在讲这样的:
按照出度排序,没有连边的点必须合并,最后找集合个数
但是合并的时候要注意用y的答案更新x,这样y就不用再跑一次了(这里的总复杂度较为诡异)
更新过程:遍历x的边,如果y的边中没有x的这条边,那么就将其删去,并且将这个点合并
首先根据鸽巢原理,出度最小的点最大出度必然是\(\frac{m}{n}\)
它的边数也是\(\frac{m}{n}\)
每次和其他的点合并,这个复杂度是 \(\frac{m}{n} \cdot m\) (事实上是远远跑不到的!因为每次都会删去大量的边!)
所以哪,是不会T的
然后由于合并完之后也就剩下不到\(\frac{m}{n}\)个点了,所以这里就算你暴力\(O(n)\)合并也没关系
最后是你们担心的\(\frac{m}{n} \cdot m\)会TLE
瞪眼一看当\(m=2e6,n\)较小时就T了
哪你n较小时直接跑\(O(n^2)\)不就是了 吐舌头
注意时限是20s的这个代码还根本跑不满,所以自然不用担心!
tips: vector可以用链表优化更棒
转载于:https://www.cnblogs.com/chasedeath/p/11258765.html
相关资源：JAVA上百实例源码以及开源项目