并查集模板

并查集的概念并查集的实现1. 初始化for (int i 1; i n; i) fa[i] i;2. 查询操作一直往上找父亲int find(int x) { if (fa[x] x) return x; return fa[x] find(fa[x]); }3. 合并操作让元素x与元素y 所在的集合合并成一个集合也就是让x所有的数指向元素y所在的树的根节点int fx find(x); int fy find(y); fa[fx] fy;4. 判断操作判断元素x和元素y是否在同一集合看看两者所在树的根节点是否相同bool issame(int x, int y) { return find(x) find(y); }题目P3367 【模板】并查集 - 洛谷并查集模板#include iostream using namespace std; const int N 2e510; int n; int fa[N]; int find(int x) { if (fa[x] x) return x; //如果 x 的父亲节点就是自己说明 x 已经是根节点了直接返回 x return fa[x] find(fa[x]); //路径压缩 递归找到x的祖先根节点再把 x 直接挂到根节点上 } int main() { int T; cin n T; for (int i 1; i n; i) fa[i] i; while(T--) { int z, x, y; cin z x y; if (z 1) //合并 { int fx find(x); //找到x所在的集合的根节点 int fy find(y); //找到y所在的集合的根节点 fa[fx] fy; //把 x的根节点挂到 y的根节点下面 } else { if (find(x) find(y)) cout Y endl; else cout N endl; } } return 0; }