经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C » 查看文章
cf1037E. Trips(图论 set)
来源:cnblogs  作者:自为风月马前卒  时间:2018/11/5 11:09:45  对本文有异议

题意

题目链接

Sol

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

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

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

如果不合法就继续删

  1. #include<bits/stdc++.h>
  2. #define Pair pair<int, int>
  3. #define MP make_pair
  4. #define fi first
  5. #define se second
  6. using namespace std;
  7. const int MAXN = 2e5 + 10;
  8. inline int read() {
  9. char c = getchar(); int x = 0, f = 1;
  10. while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
  11. while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  12. return x * f;
  13. }
  14. int N, M, K, vis[MAXN], inder[MAXN], Ans, ans[MAXN], vis2[MAXN];
  15. Pair E[MAXN];
  16. set<int> s[MAXN];
  17. void delet(int x) {
  18. if(vis[x]) return ;
  19. vis[x] = 1; Ans--;
  20. for(set<int>::iterator it = s[x].begin(); it != s[x].end(); it++) {
  21. int to = *it; //s[x].erase(*it);
  22. inder[to]--;
  23. if(inder[to] < K) delet(to);
  24. }
  25. }
  26. int main() {
  27. Ans = N = read(); M = read(); K = read();
  28. for(int i = 1; i <= M; i++) {
  29. int x = read(), y = read();
  30. s[x].insert(y); s[y].insert(x); inder[x]++; inder[y]++;
  31. E[i] = MP(x, y);
  32. }
  33. for(int i = 1; i <= N; i++) if(inder[i] < K) delet(i);
  34. for(int i = M; i >= 1; i--) {
  35. ans[i] = Ans;
  36. if(vis[E[i].fi] || vis[E[i].se]) continue;
  37. inder[E[i].fi]--; inder[E[i].se]--;
  38. s[E[i].fi].erase(E[i].se); s[E[i].se].erase(E[i].fi);
  39. if(inder[E[i].fi] < K) delet(E[i].fi);
  40. if(inder[E[i].se] < K) delet(E[i].se);
  41. }
  42. for(int i = 1; i <= M; i++) printf("%d\n", ans[i]);
  43. return 0;
  44. }
 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号