Neovim-如何使用编辑器的神

并查集模板题

https://www.acwing.com/problem/content/838/

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int p[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{

    cin >> n >> m;
    for (int i = 1; i <= n; i ++) p[i] = i;

    string op;
    int a, b;

    while (m --)
    {
        cin >> op >> a >> b;
        if (op == "M") p[find(a)] = find(b);
        else
        {
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}

连通块中点的个数

https://www.acwing.com/problem/content/839/

本题是利用并查集来维护集合中元素的个数.

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int p[N], s[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i ++) p[i] = i, s[i] = 1;

    string op;
    int a, b;

    while (m --)
    {
        cin >> op;
        if (op == "C")
        {
            cin >> a >> b;
            a = find(a), b = find(b);
            if (a != b) p[a] = b, s[b] += s[a];
        }
        else if (op == "Q1")
        {
            cin >> a >> b;
            a = find(a), b = find(b);
            if (a == b) puts("Yes");
            else puts("No");
        }
        else if (op == "Q2")
        {
            cin >> a;
            cout << s[find(a)] << endl;
        }
    }
    return 0;
}

食物链

https://www.acwing.com/problem/content/242/

本题是利用并查集维护一种环形的逻辑关系.

假设$X$吃$Y$, 并且$Y$吃$Z$, 那么根据题目要求, $Z$肯定吃$X$.

那么规定, $Z$是第0代.

• 因为$Y$吃$Z$, 所以规定$Y$是第1代.
• 因为$X$吃$Y$, 所以规定$X$是第2代.
• 那么第3代肯定和$Z$是同类

因此, 按照这个规定:

• 如果一个点到根节点的距离为1, 那么这个点吃根节点.
• 如果一个点到根节点的距离为2, 那么这个点被根节点吃.
• 如果一个点到根节点的距离在模3的意义下为0, 那么这个点和根节点同类.

这个距离可以用并查集维护.

#include <iostream>

using namespace std;

const int N = 50010;

int n, k;
int p[N], d[N];

int find(int x)
{
    if (p[x] != x)
    {
        /* 先找到根节点, 并且压缩后面的路径 */
        int t = find(p[x]);
        /* 维护距离 */
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}


int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i ++) p[i] = i;

    int res = 0;
    while (k --)
    {
        int t, x, y;
        cin >> t >> x >> y;

        /* 假话标准2 */
        if (x > n || y > n)
        {
            res ++;
            continue;
        }
        /* 如果给出的是同类的关系 */
        if (t == 1)
        {
            /* 找到x和y的父节点 */
            int px = find(x), py = find(y);
            /* 如果px == py, 那么x和y的关系一定已知 */
            if (px == py)
            {
                /* 如果d[x]和d[y]在模3的意义下距离不一样, 那么就不是同类 */
                if ((d[x] - d[y]) % 3 != 0)
                {
                    res ++;
                    continue;
                }
            }
            /* 如果px != py, 那么就需要维护x和y的关系 */
            else
            {
                p[px] = py;
                /* 距离有(d[x] + d[px] - d[y]) % 3 == 0 */
                d[px] = d[y] - d[x];
            }
        }
        /* 如果给出的是吃与被吃的关系 */
        else
        {
            int px = find(x), py = find(y);
            if (px == py)
            {
                /* x吃y, 如果是真话, 那么x肯定比y距离多1 */
                if ((d[x] - d[y] - 1) % 3 != 0)
                {
                    res ++;
                    continue;
                }
            }
            else
            {
                p[px] = py;
                /* (d[x] + d[px] - 1 - d[y]) % 3 == 0 */
                d[px] = d[y] + 1 - d[x];
            }
        }
    }
    cout << res << endl;
    return 0;
}