[TIOJ 1220] 辦公室設置

作法：

首先先把原題等價成，要求給的圖的補圖的連通塊數。因為兩坨辦公室之間必須連滿邊，所以考慮補圖會變成兩坨之間完全沒有邊，也就是他們是不同的連通分量。

當然把補圖建出來會爆掉，因為補圖是個稠密圖。我的作法是用並查集，把每個點加進來之後把並查集維護好，最後答案就是並查集的個數。

具體作法是，假設現在已經有了前 i 個點，加上補圖中和他們連邊的其他點，這些點形成的連通分量了，那麼當下一個點 x 加進來之後，如果某一個連通分量裡面的點根 x 沒有全部連滿 ( 就是 x 沒有連到所有那個連通分量的點 )的話，可以知道在補圖裡面 x 就會和那個連通分量相連。另外還要考慮「目前仍不在任何連通分量裡的點」 ( 我把這些點的 fa 值設成 -1 )，其中和 x 有連邊的會繼續被保留下來，和 x 沒連邊的就讓他的老爸等於 x 。

至於要如何知道一個連通分量是不是和 x 連滿邊，我再對每個分量多記錄了他的 size ，還有開一個 set 表示每一坨點的最老爸(?)的那個點 ( 就是那個滿足 fa[ y ] = y 的點 )，然後用 map 記錄每個連通分量和 x 連了幾條邊，如果數量 < 他的 size 就得把他和 x 合併起來。

之後查了一下別人的作法，有一種作法是因為原圖是稀疏圖，所以如果考慮度最小的點，他的度不會太大(由鴿籠原理)，也就是在捕圖裡面這個點連出了很多條邊，也就是在捕圖裡沒有和這個點相連的點蠻少的，所以可以直接暴力作剩下的點，效率似乎沒有很好，不過還是能AC。

另外一種作法就是用 linked list 優化DFS。大致上是說，假設現在要找一個稠密圖的連通分量，並且圖的鄰接矩陣開的下，那一種作法就是當DFS到每個點的時候，去試看看 1~n 有哪些點還沒被走過，並且和這個點相鄰。但實際上這個過程多耗了很多時間，如果我們可以在DFS到一個點的時候就從 1~n 裡把這個點刪掉，因為之後的DFS的時候就算有個點和他有連邊，那那個點早就被走過了(因為DFS會先把和這個點所有相鄰的點走完再出去)。而實作上就是用 linked list，這樣就可以保證這個算法是O(n+m) 的了，不過還是需要思考要怎麼處理「要DFS的圖是原題的捕圖」。

上面作法的 code 在這個網站，可以參考看看，感覺我沒有寫得很清楚OAO

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10 ;
 
vector<int> v[maxn] ;
 
int fa[maxn],size[maxn] ;
int getfa(int x)
{
    return fa[x]==x ? x : fa[x]=getfa(fa[x]) ;
}
 
set<int> fas,las,las2 ;
map<int,int> mp ;
vector<int> del ;
int type[maxn] ;
main()
{
    int n,m ; scanf("%d%d",&n,&m) ;
    while(m--)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        v[x].push_back(y) ;
        v[y].push_back(x) ;
    }
    fill(fa+1,fa+n+1,-1) ;
    for(int i=1;i<=n;i++) las.insert(i) ;
    for(int i=1;i<=n;i++)
    {
        mp.clear() ;
        las2.clear() ;
        del.clear() ;
        for(auto j : v[i])
        {
            if(fa[j]==-1)
            {
                las2.insert(j) ;
                type[j]=i ;
            }
            else mp[getfa(j)]++ ;
        }
        if(fa[i]==-1)
        {
            fa[i]=i ; size[i]=1 ;
            for(auto j : las) if(j!=i && type[j]!=i)
                fa[j]=i , size[i]++ ;
            for(auto j : fas) if(mp[j]<size[j])
            {
                fa[j]=i ;
                size[i]+=size[j] ;
                del.push_back(j) ;
            }
            for(auto j : del) fas.erase(j) ;
            fas.insert(i) ;
        }
        else
        {
            int i2=getfa(i) ;
            for(auto j : las) if(type[j]!=i)
                fa[j]=i2 , size[i2]++ ;
            for(auto j : fas) if(j!=i2 && mp[j]<size[j])
            {
                fa[j]=i2 ;
                size[i2]+=size[j] ;
                del.push_back(j) ;
            }
            for(auto j : del) fas.erase(j) ;
        }
        swap(las,las2) ;
    }
    int ans=0 ;
    for(int i=1;i<=n;i++) if(fa[i]==i || fa[i]==-1)
        ans++ ;
    printf("%d\n",ans) ;
}