题解：P11811 [PA 2015] 人赢 / Mistrzostwa

· · 题解

前言：

本篇主要介绍本题的并查集做法。如果你还不了解并查集，可以先做做 P1551 亲戚。

思路：

首先简化题意：本题要求在无向图内，找到一个任意一点出度均不小于 d 的联通子图。

直观想到的做法是：找到每个出度不小于 d 的点，判断与其相连的点出度是否符合要求，若符合，将两个点集合并。

但是这种做法有一个问题。请看以下样例：

5 4 2
1 2
1 3
2 4
3 5

很显然，该样例应该报告无解。但上述做法却会认为 1-2-3 为一个合法点集。原因就在于节点 1、2、3 出度均为 2，而事实上，并不是所有出度都应该被计算在内。例如 5 一定不可能包含在一个合法点集内，因此与其相连点的出度均要减去 1。

于是问题就转换为：我们应当如何删掉无效出度？通过分析，初始出度小于 d 的点一定无效。那么从这些点出发，其相连点出度均要减 1。若某点在删除过程中出度变得小于 d，则该点也不合法，再从该点出发重复以上步骤。该过程可以通过队列实现。

Solution：

通过以上分析，我们需要先删除无效出度，再对剩下的出度不小于 d 的点进行并查集操作。最后遍历每个并查集，找到最大点集，并升序输出其中各点。

特别地，若每个并查集的大小均不大于 d，则报告无解。

具体实现过程已在代码中注释。最后十分感谢阅读此题解。

Code：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int N = 2e5 + 10;
vector<int> g[N];
queue<int> q;
bool vis[N]; //标记是否入队
int fa[N]; //父节点
int dout[N]; //出度
int cnt[N]; //并查集计数
int n,m,d;

int find(int x) //查询x的祖先
{
    if (fa[x] == x) return x;
    else return fa[x] = find(fa[x]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> d;
    for (int i = 1 ; i <= m ; i++)
    {
        int u,v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        dout[u]++;
        dout[v]++;
    }

    for (int i = 1 ; i <= n ; i++)
    {
        fa[i] = i; //并查集初始化
        if (dout[i] < d) //出度小于d则入队
        {
            q.push(i);
            vis[i] = true;
        }
    }

    while (!q.empty()) //删除入度小于d的点
    {
        int pos = q.front();
        q.pop();

        for (int i = 0 ; i < g[pos].size() ; i++)
        {
            int to = g[pos][i];
            dout[to]--;
            if (dout[to] < d && !vis[to]) //删边后入度小于d且未入队的点入队
            {
                q.push(to);
                vis[to] = true;
            }
        }
    }

    for (int i = 1 ; i <= n ; i++)
    {
        if (dout[i] < d) continue;
        for (int j = 0 ; j < g[i].size() ; j++)
        {
            int to = g[i][j];
            if (dout[to] < d) continue;
            int r1 = find(to);
            int r2 = find(i);
            if (r1 != r2) fa[r2] = r1; //处于不同并查集则合并
        }
    }

    for (int i = 1 ; i <= n ; i++)
    {
        int r = find(i);
        cnt[r]++; //并查集大小计数
    }

    int maxn = -2e9;
    int id = 0;
    for (int i = 1 ; i <= n ; i++)
    {
        if (cnt[i] > d)
        {
            if (cnt[i] > maxn)
            {
                maxn = cnt[i];
                id = i; //符合要求的并查集编号
            }
        }
    }

    if (maxn == -2e9) cout << "NIE" << endl; //无符合要求点集则输出无解
    else
    {
        cout << maxn << endl;
        for (int i = 1 ; i <= n ; i++)
        {
            if (find(i) == id)
            {
                cout << i << " ";
            }
        }
        cout << endl;
    }

    return 0;
}