Codeforces 1037E(类似拓扑排序)

发表于 | 分类于 | | + s

Codeforces 1037E
题意：有$n$个人，$m$天，每天晚上都会有一次聚会，一个人会参加一场聚会当且仅当聚会里有至少$k$个人是他的朋友。每天早上都会有一对人成为好朋友，问每天晚上最多能有多少人参加聚会。朋友关系不满足传递性。
相当于有$n$个点，进行$m$次加边操作，每次操作后附加一个询问，问最大点集的大小，使得点集中每个点的度数均大于等于$k$

本题还是逆向思维比较容易。
我们先思考所有边加入的答案。对于一些点他的度数如果不足$k$那就肯定不能够成为点集元素，删掉他，并且删掉他所连的边。直到没有这样的点为止。剩余的点即为答案。
然后就是删边。如果该边已经被删除，那么这条边对之前的答案没有任何影响，直接输出上一个的答案即可。否则就删掉这条边并让边的两个点度数都减一，如果有度数不足$k$的就继续删并且删掉他所连的边直到没有这样的点为止。剩余的点即为答案。之后都是类推。
对于判断有度数不足$k$要用dg(u)+1==k来判断，否则可能多次记录答案导致错误

知识点：1、正难则反
2、从简单情况到复杂情况的思路

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double

const int MAXN = 200000 + 5;

struct edge {int nxt, u, v, no;} ed[MAXN * 2];

int n, m, k, ans[MAXN], vis[MAXN];
int en, hd[MAXN * 2], dg[MAXN];
std::queue<int > q;

inline void ins(int x, int y, int no) {
    ed[++en] = (edge){hd[x], x, y, no}, hd[x] = en, dg[x]++;
    ed[++en] = (edge){hd[y], y, x, no}, hd[y] = en, dg[y]++;
}

void clean() {
    ms(dg, 0), ms(hd, -1), ms(vis, 0);
}
int solve() {
    clean();
    for (int x, y, i = 1; i <= m; i++) scanf("%d%d", &x, &y), ins(x, y, i);
    ans[m + 1] = n;
    for (int i = 1; i <= n; i++) if (dg[i] < k) q.push(i), ans[m + 1]--;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = hd[u]; i > 0; i = ed[i].nxt) {
            edge &e = ed[i];
            vis[e.no] = 1, dg[e.v]--;
            if (dg[e.v] + 1 == k) q.push(e.v), ans[m + 1]--;
        }
    }
    for (int i = m; i >= 2; i--) {
        ans[i] = ans[i + 1];
        if (vis[i]) continue;
        edge &e = ed[i * 2];
        vis[e.no] = 1, dg[e.v]--, dg[e.u]--;
        if (dg[e.u] + 1 == k) q.push(e.u), ans[i]--;
        if (dg[e.v] + 1 == k) q.push(e.v), ans[i]--;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int j = hd[u]; j > 0; j = ed[j].nxt) {
                edge &e = ed[j];
                if (vis[e.no]) continue;
                vis[e.no] = 1, dg[e.v]--;
                if (dg[e.v] + 1 == k) q.push(e.v), ans[i]--;
            }
        }
    }
    for (int i = 2; i <= m + 1; i++) printf("%d\n", ans[i]);
    return 0;
}
int main() {
    scanf("%d%d%d", &n, &m, &k), solve();
    return 0;
}
------ 本文结束 ------