模拟赛题讲解[35]

题目链接：noi.ac #3714 （让 mygr 巨佬帮我交的隐藏题）

一、题面

菜汪酱发现了 \(n\) 个宝箱，编号为 1 到 \(n\)。

这些宝箱被 \(m\) 条铁链绑在了一起。每条铁链连接两个宝箱。

菜汪酱希望拿走尽可能多的宝箱。但是宝箱不能乱拿，否则会触发机关。经过解密，菜汪酱知道一种方案是安全的当且仅当：

拿走的宝箱两两之间有铁链连接。
没有拿走的宝箱两两之间没有铁链连接。

菜汪酱希望在保证安全的情况下拿走尽可能多的宝箱。这个问题的解决方案交给你了。

输入格式

第一行两个整数 \(n\) 和 \(m\)。

接下来 \(m\) 行每行两个整数 \(u\) 和 \(v\)，表示一条铁链连接宝箱 \(u\) 和 \(v\)。

保证不会有两条铁链连接相同的宝箱。

保证存在一种安全的方案。

输出格式

第一行输出一个整数 \(\rm ans\)，表示拿走的宝箱个数。

第二行输出 \(\rm ans\) 个整数，表示选择的宝箱编号。

输入输出样例

输入：

输出：

4
5 1 7 4

数据范围

对于 \(100\%\) 的数据，\(n \leq 100000\)，\(m \leq \min\left\{1000000, \frac{n(n-1)}{2}\right\}\)。

二、题解

题目实际上要我们构造最大团，这个问题本身是 NPC 的。

但是由于本题是一个稀疏图，因此实际上答案的点数是不会超过 \(1000\) 的（尽管这和正解关系不大）

考虑到很多点的度数都很小，我们将点的度数从大到小排序，考虑取某个最长的前缀作为答案。

注意这里题目保证有解，且要求剩余的点构成独立集，那么我们不可能从某个前缀中抠掉几个点作为答案。

那么现在问题就变成了，如何判断一个点集 \(S\) 合法。

可以证明，当且仅当 \(\sum_{i \in S} d_i - m = \binom{|S|}{2}\) 时，\(S\) 是一个合法的集合。

因为当 \(S\) 合法时这里 \(m+\binom{|S|}{2}\) 的含义为点集 \(S\) 的度数和，所以显然等式成立。

于是只需要扫一遍就好了。注意若当前的前缀不合法还是可以继续扫的。

时间复杂度 \(\mathcal{O}(n\log n + m)\) ，用计数排序可以做到 \(\mathcal{O}(n + m)\) 。

代码：

#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 rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e5 + 15))

struct node { int d, id; } a[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m; cin >> n >> m; rep(i, 1, n) a[i].id = i;
    rep(i, 1, m) { int u, v; cin >> u >> v; ++a[u].d; ++a[v].d; }
    sort(a + 1, a + 1 + n, [&](node x, node y) { return x.d > y.d; });
    int ans = -1, sum = 0;
    rep(i, 1, n) if((sum += a[i].d) - m == i * (i - 1) / 2) ans = i;
    cout << ans << '\n';
    rep(i, 1, ans) cout << a[i].id << " \n"[i == iEND];
    return 0;
}