并查集

# 并查集

模板题:[P3367 【模板】并查集 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/problem/P3367)

## 代码

```cpp
#include <iostream>
using namespace std;
const int MAXN = 1e4 + 5;
int fa[MAXN], rk[MAXN];
template <class T>
void read(T &r)
{
    static char ch, f;
    ch = getchar();
    r = 0;
    f = 1;
    while (ch < '-')
        ch = getchar();
    if (ch == '-')
        f = -1, ch = getchar();
    for (; ch >= '0' && ch <= '9'; ch = getchar())
        r = (r << 1) + (r << 3) + (ch - '0');
}
// 初始化
void init(int n)
{
    for (register int i = 1; i <= n; i++)
    {
        fa[i] = i;
        rk[i] = 1;
    }
}
// 路径压缩查找
int find(int p)
{
    return p == fa[p] ? p : (p = find(fa[p]));
}
// 按秩合并
void merge(int a, int b)
{
    int ar = find(a), br = find(b);
    if (rk[ar] <= rk[br])
        fa[ar] = br;
    else
        fa[br] = ar;
    if (rk[ar] == rk[br] && ar != br)
        rk[br]++;
}
int main()
{
    int n, m, z, x, y;
    read(n);
    read(m);
    init(n);
    for (register int i = 1; i <= m; i++)
    {
        read(z);
        read(x);
        read(y);
        if (z == 1)
            merge(x, y);
        else
            printf(find(x) == find(y) ? "Y\n" : "N\n");
    }
}
```

## 参考文章

[算法学习笔记(1) : 并查集 - 知乎 (zhihu.com)](https://zhuanlan.zhihu.com/p/93647900)

最后修改：2023 年 03 月 13 日