[SDOI2019]热闹又尴尬的聚会
链接
思路
第一问贪心？的从小到大删除入度最小的点，入度是动态的，打个标记。
当然不是最大独立集。
第二问第一问的顺序选独立集，不行就不要。选出来的一定是满足不等式的。
每次最多删除p+1个，独立集个数是\(\lceil \frac{n}{p+1} \rceil >= \lfloor \frac{n}{p+1} \rfloor\)
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;
int read() {
int x = 0, f = 1; char s = getchar();
for (;s > '9' || s < '0'; s = getchar()) if (s == '-') f = -1;
for (;s >= '0' && s <= '9'; s = getchar()) x = x * 10 + s - '0';
return x * f;
}
int n, m, ru[N];
vector<int> G[N];
vector<pair<int, int> > nb;
int ans1[N], vis[N];
struct edge{
int val, id;
edge(int x = 0, int y = 0) {val = x, id = y;}
};
bool operator < (edge a, edge b) {return a.val > b.val;}
priority_queue<edge> q;
void solve() {
for (int i = 1; i <= n; ++i) q.push(edge(ru[i], i));
int mx = 0;
while (!q.empty()) {
edge now = q.top();
q.pop();
if (now.val != ru[now.id]) continue;
// printf("ru[%d]=%d\n",now.id,ru[now.id]);
mx = max(mx, ru[now.id]);
ans1[now.id] = mx;
vis[now.id] = 1;
for (auto v : G[now.id]) {
if (vis[v]) vis[now.id] = 0;
if (!ans1[v]) q.push(edge(--ru[v],v));
}
}
int js = 0;
for (int i = 1; i <= n; ++i) if (ans1[i] == mx) ++js;
printf("%d ", js);
for (int i = 1; i <= n; ++i) if (ans1[i] == mx) printf("%d ", i);
printf("\n");
js = 0;
for (int i = 1; i <= n; ++i) if (vis[i]) ++js;
printf("%d ", js);
for (int i = 1; i <= n; ++i) if (vis[i]) printf("%d ", i);
printf("\n");
}
int main() {
// freopen("a.in","r",stdin);
int T = read();
while (T--) {
n = read(), m = read();
for (int i = 1; i <= n; ++i) {
G[i].clear();
vis[i] = ru[i] = ans1[i] = 0;
}
for (int i = 1; i <= m; ++i) {
int u = read(), v = read();
G[u].push_back(v), G[v].push_back(u);
ru[u]++, ru[v]++;
}
solve();
}
return 0;
}