Codeforces

Luogu

分析

倒序处理整个过程。

每次取出所有还未被删去的度数 $<k$ 的点,然后把它删去并 BFS 更新周围的点即可。

为了方便可以 vector 存边。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') w=c=='-'?-1:1,c=getchar();
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n,m,k,sum;
int x[N],y[N];
vector<int> E[N];
int del[N],deg[N];
int ans[N];

inline void expand(int s) {
    if (del[s]||deg[s]>=k) return;
    queue<int> Q; Q.push(s);
    del[s]=1,--sum;
    while (!Q.empty()) {
        int u=Q.front(); Q.pop();
        for (re int v:E[u]) {
            if (del[v]) continue;
            --deg[v];
            if (deg[v]<k) del[v]=1,--sum,Q.push(v);
        }
    }
}

int main() {
    sum=n=read(),m=read(),k=read();
    for (re int i=1;i<=m;++i) {
        x[i]=read(),y[i]=read();
        E[x[i]].push_back(y[i]),++deg[x[i]];
        E[y[i]].push_back(x[i]),++deg[y[i]];
    }
    for (re int i=1;i<=n;++i) expand(i);
    ans[m]=sum;
    for (re int i=m;i>1;--i) {
        E[x[i]].pop_back(); if (!del[y[i]]) --deg[x[i]];
        E[y[i]].pop_back(); if (!del[x[i]]) --deg[y[i]];
        expand(x[i]),expand(y[i]);
        ans[i-1]=sum;
    }
    for (re int i=1;i<=m;++i) printf("%d\n",ans[i]);
    return 0;
}
最后修改:2019 年 08 月 01 日 04 : 50 PM