[noi110]翘课

发现加边操作不好处理，因此考虑先加完所有边后删边。

删去一对边x到y，如果两者中有一个不翘课显然没有意义，那么如果都翘课了那么就对他们进行判断，如果无法翘课就继续搜下去。

这样的时间复杂度看上去似乎是o(nm)的，但注意到每一个点最多由翘课变为不翘课一次，因此是o(n+m)的。

#include<bits/stdc++.h>
using namespace std;
queue<int>q;
struct ji{
    int nex,to;
}edge[400001];
int E,n,m,k,head[200001],x[200001],y[200001],d[200001],ans[200001];
bool vis[200001],flag[400001];
void add(int x,int y){
    edge[E].nex=head[x];
    edge[E].to=y;
    head[x]=E++;
}
void pus(int t){
    if (d[t]<k){
        q.push(t);
        ans[0]-=(vis[t]=1);
    } 
}
void erase(){
    while (!q.empty()){
        int k=q.front();
        q.pop();
        for(int i=head[k];i!=-1;i=edge[i].nex)
            if ((!vis[edge[i].to])&&(!flag[i])){
                flag[i]=flag[i^1]=1;
                d[edge[i].to]--;
                pus(edge[i].to);
            } 
    }
}
int main(){
    memset(head,-1,sizeof(head));
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x[i],&y[i]);
        add(x[i],y[i]);
        add(y[i],x[i]);
        d[x[i]]++;
        d[y[i]]++;
    }
    ans[0]=n;
    for(int i=1;i<=n;i++)pus(i);
    for(int i=m;i;i--){
        erase();
        ans[i]=ans[0];
        if (vis[x[i]]+vis[y[i]]==0){
            d[x[i]]--;
            d[y[i]]--;
        }
        flag[i*2-1]=flag[i*2-2]=1;
        if (!vis[x[i]])pus(x[i]);
        if (!vis[y[i]])pus(y[i]);
    }
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
}