洛谷P5361 [SDOI2019] 热闹的聚会与尴尬的聚会题解

题目链接：P5361 [SDOI2019] 热闹的聚会与尴尬的聚会

题意：

小 Q 的生日快到了，他决定周末邀请一些朋友到他的新房子一起聚会！

他的联系薄上有 $n$ 位好友，他们两两之间或者互相认识，或者互相不认识。小 Q 希望在周六办一个热闹的聚会，再在周日办一个尴尬的聚会。

一场热闹度为 $p$ 的聚会请来了任意多位好友，对于每一位到场的好友来说都有至少 $p$ 位他认识的好友也参加了聚会，且至少对于一位到场的好友来说现场恰好有 $p$ 位他认识的好友；

一场尴尬度为 $q$ 的聚会请来了恰好 $q$ 位好友，且他们两两互不认识。

两场聚会可能有重复的参与者，联系薄上也有可能有某些好友同时缺席了两场聚会。

小 Q 喜欢周六聚会的热闹度 $p$ 与周日聚会的尴尬度 $q$ 之间满足：$\left\lfloor \frac{n}{p+1} \right\rfloor \le q$ 且 $\left\lfloor \frac{n}{q+1} \right\rfloor \le p$。

请帮助小 Q 找出一个可行的邀请方案。

输入格式：

输入含有多组测试数据，并在第一行给定一个整数 $T$，表示总共有多少组测试数据。之后依次给出每一组数据。

每一组测试数据第一行给定两个整数 $n$ 和 $m$，依次表示联系薄中好友的总数，以及有多少对互相认识的好友。

之后 $m$ 行每行给定两个正整数 $u$ 和 $v$，满足 $1\le u\neq v\le n$ ，表示第 $u$ 个好友与第 $v$ 个好友互相认识。

输出格式：

对于每一组数据输出两行，依次描述周六热闹的聚会的参加人员，与周日尴尬的聚会的参加人员列表：

第一行先输出一个正整数表示总共邀请来了多少位好友参加周六的聚会，再之后输出若干个不同的整数，按照任意顺序描述被邀请的是哪些好友。

第二行先输出一个正整数表示总共邀请来了多少位好友参加周日的聚会，再之后以任意顺序输出若干个不同的整数，同样描述了周日被邀请的好友。

如果有多组方案，你可以输出其中任何一组。

数据范围：

$1\le T\le 32,~1\le m\le 10^5,~1 \le n \le 10^4$。

本题要求构造一个度数均大于等于 $p$ 的导出子图，并构造一个大小为 $q$ 的独立集，同时满足

$\left\lfloor \frac{n}{p+1} \right\rfloor \! \le q \, \land \, \left\lfloor \frac{n}{q+1} \right\rfloor \! \le p$

先分析一下这个奇怪的式子

如果 $\left\lfloor \frac{n}{p+1} \right\rfloor \not\in \mathbb{Z}$ ，则 $\frac{n}{p+1}<q+1 \Leftrightarrow \frac{n}{q + 1} < p + 1$ ，显然满足 $\left\lfloor \frac{n}{q+1} \right\rfloor \le p$ 。
如果 $\left\lfloor \frac{n}{p+1} \right\rfloor \in \mathbb{Z}$ ，则 $\frac{n}{p+1} \le q \Leftrightarrow \frac{n}{p+1} < q + 1$ ，然后又满足 $\left\lfloor \frac{n}{q+1} \right\rfloor \le p$ 了。

于是这两个条件是等价的。

那么一个简单的想法是，我们只需要让 $p,q$ 都取到最大值，这个条件就满足了。

让 $p$ 取最大值的构造很简单，我们每次在图上删除度数最小的点和它的边，然后更新答案即可。

而让 $q$ 取最大值的构造就不容易了，一般图最大独立集是 NPC 问题，只能用模拟退火等办法近似。

不过，既然这题是第二问，并且 $p,q$ 都取到最大值只是题目限制的一个必要条件

那么构造方式一定与第一问有所联系。

有意思的是，第一问的构造方式提示我们，这个独立集很可能与我们删去的那些点有关

我们把删去的第一个点放入独立集，那么与它相连的那些节点一定不能加入独立集，可以将他们删去

而非常棒的是，我们接下来取出的那个点一定与这个点没有任何边，否则在上一步被删除了。

考虑重复这样的过程，则一定可以构造一个独立集。问题是，它满足 $\left\lfloor \frac{n}{p+1} \right\rfloor \le q$ 吗？

由于我们已经求出 $p$ 的最大值了，所以每次操作删除的点数不超过 $p+1$ （$+1$ 指我们放入独立集的那个点）

因为操作次数为 $q$ ，每次都删除 $p+1$ 个点可以使 $q$ 取到最小值 $q=\left\lceil\frac{n} {p+1}\right\rceil \ge \left\lfloor \frac{n}{p+1} \right\rfloor$ ，所以构造满足条件。

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(1e4 + 15))

char vis[N];
int tot1, tot2, ansp, ansq, pos, ans1[N], ans2[N], d[N], tmp[N];
struct node { int x, y; };
bool operator<(node a, node b) { return a.y > b.y; }
priority_queue<node> q; vector<int> vec[N];
void solve()
{
    int n, m; cin >> n >> m;
    ansp = ansq = pos = tot1 = tot2 = 0;
    for(int i = 1; i <= n; i++) { vec[i].clear(), d[i] = 0; }
    for(int i = 1, u, v; i <= m; i++)
    {
        cin >> u >> v;
        vec[u].push_back(v); ++d[v];
        vec[v].push_back(u); ++d[u];
    }
    for(int i = 1; i <= n; i++) { q.push({i, d[i]}), tmp[i] = d[i], vis[i] = false; }
    ansp = q.top().y;
    while(!q.empty())
    {
        auto [u, t] = q.top(); q.pop();
        if(vis[u]) continue; vis[u] = true; ans1[++tot1] = u;
        if(t > ansp) { ansp = t; pos = tot1; }
        for(int v : vec[u]) q.push({v, --tmp[v]});
    }
    for(int i = 1; i <= n; i++) { q.push({i, d[i]}), vis[i] = false; }
    while(!q.empty())
    {
        auto [u, t] = q.top(); q.pop();
        if(vis[u]) continue; vis[u] = true; ans2[++tot2] = u;
        for(int v : vec[u]) vis[v] = true;
    }
    ansq = tot2;
    for(int i = 1; i <= n; i++) vis[i] = false;
    for(int i = 1; i <= pos; i++) vis[ans1[i]] = true;
    cout << n - pos << ' ';
    for(int i = 1; i <= n; i++) if(!vis[i]) cout << i << ' ';
    cout << '\n' << ansq << ' ';
    for(int i = 1; i <= ansq; i++) cout << ans2[i] << " \n"[i == ansq];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}