并查集

使用场景:

1. 合并两个集合
2. 查询某个元素的“所属”（祖宗节点）

记录:

1. 每个元素的大小: 绑定到root
2. 每个点到root的距离: 绑定到 每个元素 上

回顾模板:

int find(int x) // 查找x的祖先节点 (root)
{
    // 并查集: 只有 root 节点的 p[x]==x
    if (p[x] != x) p[x] = find(p[x]); // 上行
    return p[x];
}

1250 格子游戏

Alice和Bob玩了一个古老的游戏：首先画一个 n×n 的点阵（下图 n=3）

接着，他们两个轮流在相邻的点之间画上红边和蓝边：

直到围成一个封闭的圈（面积不必为 1）为止，“封圈”的那个人就是赢家。因为棋盘实在是太大了，他们的游戏实在是太长了！

他们甚至在游戏中都不知道谁赢得了游戏。

于是请你写一个程序，帮助他们计算他们是否结束了游戏？

"二维矩阵" 转换成 "一维数组": (x,y) ---> x*n+y

观察

观察题意：发现我们要判断画完线后有没有围成环

而如果能围成一个环，那么最后画的线的两个端点必然已经在一个连通块内

判断是否在一个连通块 —— 使用并查集

算法步骤如下：

• 如果两个端点已经在同一个集合 (find操作)，那么成环
• 如果两个端点不在同一个集合内 (find操作)，那么这两个集合连通，合并两个集合 (merge操作)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 40009;
int n, m, p[N]; // p[] 专用于 并查集

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

void merge(int x, int y)
{
    p[find(x)] = find(y);
}

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

    // 并查集 初始化
    for(int i = 1;i <= n * n;++ i) p[i] = i;

    char c;
    for(int i = 1, a, b;i <= m;++ i)
    {
        cin >> a >> b >> c; // 注意这不是输入的点的坐标

        int x = (a - 1) * n + b, y; // 点的坐标
        if(c == 'D') y = a * n + b; // 向下连边
        else y = (a - 1) * n + b + 1; // 向右连边

        if(find(x) == find(y)) // 如果在同一格子内
        {
            cout << i << endl;
            return 0;
        }
        merge(x, y); // 合并两个集合
    }
    cout << "draw" << endl;
    return 0;
}

1252 搭配购买

Joe觉得云朵很美，决定去山上的商店买一些云朵。

商店里有 n 朵云，云朵被编号为 1,2,…,n，并且每朵云都有一个价值。

但是商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这朵云有搭配的云都要买。

但是Joe的钱有限，所以他希望买的价值越多越好。

分析

• 本质: 一个连通块内部的元素，要么全买，要么全不买
• 思路: 将“总体积”and“总价值”绑定到root，之后遍历只需要考察 p[x] == x 节点

#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 1e4+10;

int n, m, ww;
int a[maxn];
int w[maxn]; // 价格
int v[maxn]; // 价值
int f[maxn]; // 01背包
int p[maxn]; // 并查集

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

int main()
{
    cin >> n >> m >> ww;
    for (int i=1; i<=n; i++) cin >> w[i] >> v[i];

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

    // 先处理"归属类别"关系 - 并查集
    for (int i=1; i<=m; i++)
    {
        int a, b;
        cin >> a >> b;

        int pa = find(a);
        int pb = find(b);

        if (pa != pb)
        {
            // root_b 纳入 root_a
            v[pa] += v[pb];
            w[pa] += w[pb];
            p[pb] = pa;
        }
    }

    // 再进行物品选择 - 01背包
    for (int i=1; i<=n; i++)
    {
        if (p[i] != i) continue;
        for (int j=ww; j>=w[i]; j--)
        {
            f[j] = max(f[j], f[j-w[i]] + v[i]);
        }
    }

    cout << f[ww] <<endl;
    return 0;
}

237 程序自动分析

观察数据范围, 需要“离散化”处理

离散化的要求:

• 保序: 排序 + 判重 + 二分
• 不要求保序:
  • map
  • hash table: #include <unordered_map>

不保序离散化模板

#include <unordered_map> // hash table

unordered_map<int, int> S;

int get(int x) // 对 x 进行: 不保序离散化
{
    if (S.count(x) == 0) S[x] = ++ n;
    return S[x];
}

代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 200010;

int n, m;
int p[N];
unordered_map<int, int> S;

struct Query
{
    int x, y, e;
}query[N];

int get(int x) // 不保序离散化
{
    if (S.count(x) == 0) S[x] = ++ n;
    return S[x];
}

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

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        n = 0;
        S.clear();
        scanf("%d", &m);
        for (int i = 0; i < m; i ++ )
        {
            int x, y, e;
            scanf("%d%d%d", &x, &y, &e);
            query[i] = {get(x), get(y), e};
        }

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

        // 合并所有相等约束条件
        for (int i = 0; i < m; i ++ )
            if (query[i].e == 1)
            {
                int pa = find(query[i].x), pb = find(query[i].y);
                p[pa] = pb;
            }

        // 检查所有不等条件
        bool has_conflict = false;
        for (int i = 0; i < m; i ++ )
            if (query[i].e == 0)
            {
                int pa = find(query[i].x), pb = find(query[i].y);
                if (pa == pb)
                {
                    has_conflict = true;
                    break;
                }
            }

        if (has_conflict) puts("NO");
        else puts("YES");
    }

    return 0;
}

238 银河英雄传说

维护到 “根节点” 的距离

分析:

分析:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 30010;

int m;
int p[N], sz[N], d[N];

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

int main()
{
    scanf("%d", &m);

    for (int i = 1; i < N; i ++ )
    {
        p[i] = i;
        sz[i] = 1;
    }

    while (m -- )
    {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if (op[0] == 'M')
        {
            int pa = find(a), pb = find(b);
            if (pa != pb)
            {
                d[pa] = sz[pb];
                sz[pb] += sz[pa];
                p[pa] = pb;
            }
        }
        else
        {
            int pa = find(a), pb = find(b);
            if (pa != pb) puts("-1");
            else printf("%d\n", max(0, abs(d[a] - d[b]) - 1));
        }
    }

    return 0;
}