当前位置: 代码迷 >> 综合 >> 【codefroces 1037 E Trips】【图论】【逆向思维】【好】【度大于等于k的最大子图】
  详细解决方案

【codefroces 1037 E Trips】【图论】【逆向思维】【好】【度大于等于k的最大子图】

热度:65   发布时间:2024-01-04 11:47:19.0

【链接】

https://codeforces.com/problemset/problem/1037/E

【题意】

有n个人,一开始都不是朋友,m天每天都会有x,y成为朋友,现在他们有trip,只有他们出去玩的朋友数大于等于k才能出去,求每天出去最多的人数。朋友关系不具有传递性

【思路】

用set维护图,并记录与点相连的边集。如果图从无到有建边,那么每加入一条边会导致与端点有边的所有点都需要修改,并且不容易判断,计数每天最大的size,那么我们可能逆向思维。先建好全图,将不符合的点删去。从后往前删边,只需要删去边集与点集,size的大小就是答案了

【代码】

#include<bits./stdc++.h>
using namespace std;
const int maxn = 2e5 + 6;
struct node {int x, y, ans;
}t[maxn];set<int>st;
set<int>v[maxn];
int n, m, k;void del(int x) {if (v[x].size() < k&&st.erase(x)) {for (auto &y : v[x]) {v[y].erase(x);del(y);}}
}int main() {scanf("%d%d%d", &n, &m, &k);for (int i = 1; i <= m; i++) {scanf("%d%d", &t[i].x, &t[i].y);v[t[i].x].insert(t[i].y);v[t[i].y].insert(t[i].x);}for (int i = 1; i <= n; i++) {st.insert(i);}for (int i = 1; i <= n; i++) {del(i);}for (int i = m; i; i--) {t[i].ans = st.size();if (st.size() == 0)break;v[t[i].x].erase(t[i].y);v[t[i].y].erase(t[i].x);del(t[i].x);del(t[i].y);}for (int i = 1; i <= m; i++) {printf("%d\n", t[i].ans);}
}

 

  相关解决方案