TIOJ::1890 . 【Gate】這個笑容由我來守護

http://tioj.ck.tp.edu.tw/problems/1890

這題是我出的。題目是圖論。順便交TOI一階的作業。
題目要求你求出一張圖的連通塊有多少個，會動態加入跟刪除點。

題目說有些人目標相同，有些不確定，所以我們可以透過兩個點是否連通來確定兩個人目標是不是一樣的。因為答案是連通塊數量，所以在加邊減邊的時候維護連通塊是否增加減少就可以了。

最樸素的作法就是每次加邊就先DFS一次檢查兩個點是否連通，是就不用減少連通塊數量，不然你就會合併兩個不連通的連通塊。刪邊也一樣，刪完看看兩個點是不是被切斷了。
這樣複雜度是M*（N+M），因為會加入M次邊，每次DFS複雜度N+M。

這題N是500，M是50萬，所以很顯然會爆炸。
所以再想想，一開始我有想過可分裂並查集，不過看來沒有什麼用，因為可分裂並查集不能路徑壓縮，複雜度會退話，而且很難寫。不過由此我們可以想到一個還不錯的作法。

首先，DFS複雜度會是N+M是因為可能會遍歷每條邊和點，但我們其實只想知道兩點是否有連通，所以我們只需要連通塊的生成樹就可以了，並不需要多餘的邊。如果每個連通塊都只有生成樹，那DFS的複雜度就變成N了，再用上面的作法複雜度就會變成N*M，就能AC了。

但是我們要怎麼決定要去掉哪些邊、要留下哪些邊？
觀察一下，我們發現每條邊都有一個出生時間和死亡時間（一開始的邊出生時間是0，最後沒被刪除的邊，死亡時間是無限大），當我們加入邊的時候，就直接加入，除非加入這條邊會產生環，那我們就將環上死亡時間最早的邊預先刪除，這樣就能保證生成樹的正確性，也可以求出答案了。

實作上，因為會有重邊，我開了一排queue來維護某個位置（兩個點之間）的邊的死亡時間，加邊就如上面所說，刪邊則要先確定是不是已經刪除過了，我是透過這個位置被預先刪除了幾個邊來維護。

#include <bits/stdc++.h>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
using namespace std;
const int N = 501, M = 500001;
queue<int> DIE[N*N];
int CUT[N*N];
set<int> G[N];
bool wed[N];
struct Query{
    bool q;
    int a,b;
}D[M];
inline int getEid(int a,int b,int n){
        if(a>b)swap(a,b);
        return a*n+b;
    }
inline int getTime(int x){
    return DIE[x].empty()?M:DIE[x].front();
}
int DFS(int now,int no, int end, int n){
    wed[now] = true;
    if(now == end){
        return no == -1?0:getEid(now,no,n);
    }
    for(int p:G[now]){
        if(p!=no){
        assert(!wed[p]);
        int tmp = DFS(p,now,end,n);
        if(tmp!=-1){
            return (no == -1 || getTime(tmp) < getTime(getEid(now,no,n)))?tmp:getEid(now,no,n);
        }}
    }
    return -1;
}
void link(int a,int b){
    G[a].insert(b);
    G[b].insert(a);
}
void cut(int a, int b,int n){
    int tmp = getEid(a,b,n);
    if(!DIE[tmp].empty())DIE[tmp].pop();
    G[a].erase(b);
    G[b].erase(a);
}
main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t,n,m,q,a,b;
    cin>>t;
    while(t--){
        cin>>n>>m>>q;
        memset(CUT,0,sizeof(CUT));
        fill(DIE,DIE+n*2,queue<int>());
        F(n)G[i].clear();
        F(m){
            cin>>D[i].a>>D[i].b;
            D[i].q = true;
        }
        char c;
        F(q){
            cin>>c>>D[i+m].a>>D[i+m].b;
            D[i+m].q = c=='N';
            if(!D[i+m].q){
                DIE[getEid(D[i+m].a,D[i+m].b,n)].push(i);
            }
        }
        int ans = n;
        F(m+q){
            memset(wed,0,sizeof(wed));
            if(D[i].q){
                int tmp = DFS(D[i].a, -1, D[i].b, n);
                if(tmp != -1){
                    int now = getEid(D[i].a,D[i].b,n);
                    if(getTime(now) > getTime(tmp)){
                        CUT[tmp]++;
                        cut(tmp/n,tmp%n, n);
                        link(D[i].a,D[i].b);
                    }else{
                        CUT[now]++;
                        if(!DIE[now].empty())DIE[now].pop();
                    }
                }else{
                    link(D[i].a,D[i].b);
                    ans--;
                }
            }else{
                int tmp = getEid(D[i].a,D[i].b,n);
                if(CUT[tmp]){
                    CUT[tmp]--;
                }else{
                    cut(D[i].a,D[i].b, n);
                    if(DFS(D[i].a, -1, D[i].b, n)==-1)ans++;
                }
            }
            if(i>=m)cout<<ans<<'\n';
        }
    }
}