[POI 14 Stage 1]Offices

仔細想想，可以發現最大辦公大樓數量就是補圖的連通塊數量，每棟辦公大樓的大小就是這些連通塊的大小

所以把補圖建出來就好了

等等，$N$到100000...

可以發現，我們只須在意連通性，因此如果$A$能走到$B$和$C$，就不必考慮$B$有沒有邊連向$C$了
也就是說，我們只需要挑出幾條代表性的邊，讓連通性保持不變就好了

實作上可以每次挑一個沒走過的點$u$開始bfs，遍歷所有未走過的點，和$u$有連邊的時候跳過，否則加入queue裡面並標記已走過

這做法看似不太高效，但是因為這是稀疏圖，跳過的次數不會超過$M$次，如果將鄰接表和未走過的點都用set維護的話，時間複雜度可以達到$O((N+M)\log N)$

就這樣傳上去獲得了39分+一堆RE
記憶體超限= =

因此我把雙向邊當作單向邊來存，這樣記憶體就少一半了

獲得了88分+一堆OK(?)
沒跟我解釋為啥沒滿分= =

自己生10W點200W邊的測資，開了工作管理員測一下記憶體
只見記憶體用量慢慢往上飆
就在最後一刻
閃了一個65180KB
答案就跑出來了Orz
可是記憶體限制64MB......

至於後來我怎麼成功把記憶體降到20MB並獲得滿分
請看我的code吧XD

時間複雜度：$O((N+M)\log N)$

code:

#include<cstdio>
//#include<cassert>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
using namespace std;
void assert(bool valid){if(valid)return;for(;;)putchar('E');}
bool Contains(const vector<int>&s,const int v)
{
    const int i=lower_bound(s.begin(),s.end(),v)-s.begin();
    return i<(int)s.size()&&s[i]==v;
}
int N,M;
vector<int>ET[100000];
set<int>REMAIN;
int Bfs()
{
    int ans=0;
    static queue<int>q;assert(q.empty());
    q.push(*REMAIN.begin()),REMAIN.erase(REMAIN.begin());
    while(!q.empty())
    {
        const int u=q.front();q.pop();
        ans++;
        for(set<int>::iterator it=REMAIN.begin();it!=REMAIN.end();)
        {
            if(!Contains(ET[u],*it)&&!Contains(ET[*it],u))
            {
                set<int>::iterator tmp=it++;
                q.push(*tmp),REMAIN.erase(tmp);
            }
            else it++;
        }
    }
    return ans;
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&N,&M)==2)
    {
        assert(2<=N&&N<=100000&&1<=M&&M<=2000000);
        for(int i=0;i<N;i++)ET[i].clear();
        for(int i=0,a,b;i<M;i++)
        {
            scanf("%d%d",&a,&b),a--,b--;
            assert(0<=a&&a<N&&0<=b&&b<N);
            ET[a].push_back(b);
        }
        for(int i=0;i<N;i++)sort(ET[i].begin(),ET[i].end());
        REMAIN.clear();
        for(int i=0;i<N;i++)REMAIN.insert(i);
        vector<int>ans;
        while(!REMAIN.empty())ans.push_back(Bfs());
        printf("%d\n",(int)ans.size());
        sort(ans.begin(),ans.end());
        for(int i=0;i<(int)ans.size();i++)
        {
            if(i)putchar(' ');
            printf("%d",ans[i]);
        }
        puts("");
        break;
    }
    return 0;
}