[POI XIV Stage I][TIOJ 1220][Disjoint Set] Offices(辦公室設置)

原題連結
詳細的題解可以直接參考這篇
我看到這題的第一直覺就是直接找度數最小的點然後拔掉，剩下的暴力去做，而這樣的作法的確是可行的。效率其實比上面那篇原本的作法還快。

其實有一些題目的作法都有這種神奇的解法會需要先對度數最小/大的點做些什麼，或是依照度數大小進行，在平面圖上有關點度數的作法更是各種多變。

在一般圖上依靠點度數的算法比較少見，但是認真分析之後通常可以獲得可接受的複雜度，證明時常需要一些數學知識，對於像我這種數學渣來說比較困難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':' ');
}