算法学习——并查集

扁平化，小挂大~

1.头文件和定义

#include<iostream> #include<stack> //使用栈实现路径压缩 using namespace std; const int N = 2e5 + 10; int father[N]; // 父节点数组，father[i]表示i的父节点 int siz[N]; // 集合大小数组，siz[i]表示以i为根的集合大小 int n, m; // n:元素个数，m:操作次数

2.初始化

void build() { for (int i = 1;i <= n;i++) // 遍历所有元素 { father[i] = i; // 每个元素的父节点初始化为自己 siz[i] = 1; // 每个集合初始大小为1 } }

3.查找

int find(int i) { stack <int> st; // 创建栈，存储路径上的节点 // 第一步：找到根节点，同时记录路径 while (i != father[i]) // 当i不是自己的父节点（不是根） { st.push(i); // 将当前节点压入栈 i = father[i]; // 向上移动到父节点 } // 此时i是根节点 // 第二步：路径压缩（扁平化） while (!st.empty()) // 当栈不为空 { int t = st.top(); // 取出栈顶节点 father[t] = i; // 将该节点的父节点直接指向根节点 st.pop(); // 弹出栈顶 } return i; // 返回根节点 }

4.判断是否在同一集合

bool is_same_set(int x, int y) { return find(x) == find(y); // 比较两个元素的根节点是否相同 }

5.合并

bool Union(int x, int y) { int fx = find(x); // 找到x的根 int fy = find(y); // 找到y的根 if (fx != fy) // 如果不在同一集合 { // 小挂大（按秩合并） if (siz[fx] > siz[fy]) // 如果fx的集合更大 { father[fy] = fx; // 将fy挂到fx下 siz[fx] += siz[fy]; // 更新fx的大小 } else // 如果fy的集合更大或相等 { father[fy] = fx; siz[fy] += siz[fx]; } return true; // 合并成功 } else return false; // 已经在同一集合，无需合并 }

6.主函数

int main() { cin >> n >> m; // 读取元素个数和操作次数 build(); // 初始化并查集 while (m--) // 处理m个操作 { int opt = 0; cin >> opt; // 操作类型：1-合并，2-查询 int x = 0, y = 0; cin >> x >> y; // 读取两个元素 if (opt == 1) // 合并操作 Union(x, y); if (opt == 2) // 查询操作 { if (is_same_set(x, y)) cout << "Y" << endl; // 在同一集合 else cout << "N" << endl; // 不在同一集合 } } return 0; }

P3367 【模板】并查集

题目背景

本题数据范围已经更新到 1≤N≤2×105，1≤M≤106。

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式

第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。

接下来 M 行，每行包含三个整数 Zi​,Xi​,Yi​ 。

当 Zi​=1 时，将 Xi​ 与 Yi​ 所在的集合合并。

当 Zi​=2 时，输出 Xi​ 与 Yi​ 是否在同一集合内，是的输出Y；否则输出N。

输出格式

对于每一个 Zi​=2 的操作，都有一行输出，每行包含一个大写字母，为Y或者N。

输入输出样例

输入 #1复制

4 7 2 1 2 1 1 2 2 1 2 1 3 4 2 1 4 1 2 3 2 1 4

输出 #1复制

N Y N Y

说明/提示

对于 15% 的数据，N≤10，M≤20。

对于 35% 的数据，N≤100，M≤103。

对于 50% 的数据，1≤N≤104，1≤M≤2×105。

对于 100% 的数据，1≤N≤2×105，1≤M≤106，1≤Xi​,Yi​≤N，Zi​∈{1,2}。

#include<iostream> #include<stack> using namespace std; const int N = 2e5 + 10; int father[N]; int siz[N]; int n, m; void build() { for (int i = 1;i <= n;i++) { father[i] = i; siz[i] = 1; } } int find(int i) { stack <int> st; //扁平化 while (i != father[i]) { st.push(i); i = father[i]; } while (!st.empty()) { int t = st.top(); father[t] = i; st.pop(); } return i; } bool is_same_set(int x, int y) { return find(x) == find(y); } bool Union(int x, int y) { int fx = find(x); int fy = find(y); if (fx != fy) { //小挂大 if (siz[fx] > siz[fy]) { father[fy] = fx; siz[fx] += siz[fy]; } else { father[fy] = fx; siz[fy] += siz[fx]; } return true; } else return false; } int main() { cin >> n >> m; build(); while (m--) { int opt = 0; cin >> opt; int x = 0, y = 0; cin >> x >> y; if (opt == 1) Union(x, y); if (opt == 2) { if (is_same_set(x, y)) cout << "Y" << endl; else cout << "N" << endl; } } return 0; }