Loading... # 并查集 模板题:[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 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 0 如果觉得我的文章对你有用,请随意赞赏