詳細的題解可以直接參考這篇
我看到這題的第一直覺就是直接找度數最小的點然後拔掉,剩下的暴力去做,而這樣的作法的確是可行的。效率其實比上面那篇原本的作法還快。
其實有一些題目的作法都有這種神奇的解法會需要先對度數最小/大的點做些什麼,或是依照度數大小進行,在平面圖上有關點度數的作法更是各種多變。
在一般圖上依靠點度數的算法比較少見,但是認真分析之後通常可以獲得可接受的複雜度,證明時常需要一些數學知識,對於像我這種數學渣來說比較困難XD。但是可以肯定的是,如果想到了一個解法本來時間複雜度是爛掉的,但是能夠透過讓他基於度數進行而「感覺快一點點」的話,不妨直接寫下來,說不定時間複雜度其實是好的!
#include<cstdio> #include<cstdlib> #include<algorithm> #include<vector> using namespace std; const int maxn=100000+5; vector<int> G[maxn]; int pri[maxn],vis[maxn],fa[maxn],size[maxn],show[maxn],showcnt=0; int findset(int x) {return x==fa[x]?x:fa[x]=findset(fa[x]);} bool cmp(const int& a,const int& b) {return G[a].size()<G[b].size();} int main() { int n,m; scanf("%d%d",&n,&m); for(int i=0;i<n;i++) pri[i]=i,fa[i]=i,size[i]=1; for(int i=0,a,b;i<m;i++) { scanf("%d%d",&a,&b);a--,b--; G[a].push_back(b); G[b].push_back(a); } sort(pri,pri+n,cmp); for(int i=0;i<n;i++) { showcnt++; int x=pri[i]; if(vis[x]) continue; show[x]=showcnt; for(int j=0;j<G[x].size();j++) show[G[x][j]]=showcnt; for(int j=0;j<n;j++) if(show[j]!=showcnt && findset(x)!=findset(j)) { size[findset(x)]+=size[findset(j)]; fa[findset(j)]=findset(x); if(i==0) vis[j]=1; } } vector<int> vec; showcnt++; for(int i=0;i<n;i++) if(show[findset(i)]!=showcnt) {vec.push_back(size[findset(i)]);show[findset(i)]=showcnt;} printf("%d\n",(int)vec.size()); sort(vec.begin(),vec.end()); for(int i=0;i<vec.size();i++) printf("%d%c",vec[i],i==vec.size()-1?'\n':' '); }
沒有留言:
張貼留言