c/c++语言开发共享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("%dn", ans[i]);     return 0; }