设为首页 加入收藏

TOP

cf1037E. Trips(图论 set)
2018-11-04 16:08:42 】 浏览:22
Tags:cf1037E. Trips 图论 set

题意

题目链接

Sol

倒着考虑!倒着考虑!倒着考虑!

显然,一个能成为答案的子图一定满足,其中任意节点的度数\(>= k\)

那么倒着维护就只用考虑删除操作,如果一个点不合法的话就把它删掉,然后考虑与他相邻的点

如果不合法就继续删

#include<bits/stdc++.h>
#define Pair pair<int, int>
#define MP make_pair 
#define fi first
#define se second 
using namespace std;
const int MAXN = 2e5 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, K, vis[MAXN], inder[MAXN], Ans, ans[MAXN], vis2[MAXN];
Pair E[MAXN];
set<int> s[MAXN];
void delet(int x) {
    if(vis[x]) return ;
    vis[x] = 1; Ans--;
    for(set<int>::iterator it = s[x].begin(); it != s[x].end(); it++) {
        int to = *it; //s[x].erase(*it);
        inder[to]--;
        if(inder[to] < K) delet(to);
    }
}
int main() {
    Ans = N = read(); M = read(); K = read();
    for(int i = 1; i <= M; i++) {
        int x = read(), y = read();
        s[x].insert(y); s[y].insert(x); inder[x]++; inder[y]++;
        E[i] = MP(x, y);
    }
    for(int i = 1; i <= N; i++) if(inder[i] < K) delet(i);
    for(int i = M; i >= 1; i--) {
        ans[i] = Ans;
        if(vis[E[i].fi] || vis[E[i].se]) continue;
        inder[E[i].fi]--; inder[E[i].se]--;
        s[E[i].fi].erase(E[i].se); s[E[i].se].erase(E[i].fi);
        if(inder[E[i].fi] < K) delet(E[i].fi); 
        if(inder[E[i].se] < K) delet(E[i].se);
    }
    for(int i = 1; i <= M; i++) printf("%d\n", ans[i]);
    return 0;
}

编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇洛谷11月月赛题解(A-C) 下一篇c++模板参数——数值类型推断

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(214) }