CF1037E Trips

题意

一共有(n)个人，他们开始互不认识，而每天早上不认识的两个人会变成朋友。一共有(m)天，每天晚上有的人要去旅行，去旅行的人必须满足ta有至少(k)个朋友也去旅行
求每天去旅行的最大人数

题解

首先考虑一个朴素暴力：
对于每次询问，在原图上不断删点，直到没有点的度小于k。
复杂度O(nm)

然后有一个简单的优化方法，我们发现，随着边的增多，留下的点会不断变多。那么从后往前，随着边的减少，留下的点会不断减少，且之前就被淘汰的点在后续状态中不可能被保留。
也就是说如果我们从后往前处理询问，每次处理出答案之后保留这个残余图，下次操作在残余图上操作，那么每个点最多被删除一次，每条边最多被遍历2次。
用队列模拟一下，复杂度O(n + m)

#include<bits/stdc++.h>
using namespace std;
#define R register int
#define AC 200100
#define ac 400100

int n, m, k, rnt, head, tail;
int Head[AC], date[ac], Next[ac], id[ac], tot;
int ans[AC], in[AC], q[AC];
bool vis[AC], z[AC];
struct node{int x, y;}way[AC];

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

inline void upmin(int &a, int b) {if(b < a) a = b;}
inline void upmax(int &a, int b) {if(b > a) a = b;}

inline void add(int f, int w, int S)
{
    date[++ tot] = w, Next[tot] = Head[f], Head[f] = tot, in[w] ++, id[tot] = S;
    date[++ tot] = f, Next[tot] = Head[w], Head[w] = tot, in[f] ++, id[tot] = S;
}

void clear()
{
    while(head < tail)
    {
        int x = q[++ head];
        -- rnt;
        for(R i = Head[x]; i; i = Next[i])
        {
            int now = id[i];
            if(vis[now]) continue;
            vis[now] = 1, -- in[way[now].x], -- in[way[now].y];
            if(!z[way[now].x] && in[way[now].x] < k) z[way[now].x] = 1, q[++ tail] = way[now].x;
            if(!z[way[now].y] && in[way[now].y] < k) z[way[now].y] = 1, q[++ tail] = way[now].y;
        }
    }
    head = tail = 0;
}

void pre()
{
    n = read(), m = read(), k = read(), rnt = n;
    for(R i = 1; i <= m; i ++) 
        way[i].x = read(), way[i].y = read(), add(way[i].x, way[i].y, i);
}

void work()
{
    for(R i = 1; i <= n; i ++) if(in[i] < k) q[++ tail] = i, z[i] = 1;
    clear(), ans[m] = rnt;
    for(R i = m; i; i --)
    {
        if(vis[i]) {ans[i - 1] = ans[i]; continue;}
        -- in[way[i].x], -- in[way[i].y], vis[i] = 1;
        if(!z[way[i].x] && in[way[i].x] < k) z[way[i].x] = 1, q[++ tail] = way[i].x;
        if(!z[way[i].y] && in[way[i].y] < k) z[way[i].y] = 1, q[++ tail] = way[i].y;
        clear(), ans[i - 1] = rnt;
    }
    for(R i = 1; i <= m; i ++) printf("%d
", ans[i]);
}

int main()
{
//	freopen("in.in", "r", stdin);
    pre();
    work();
//	fclose(stdin);
    return 0;
}