扁平化，小挂大~
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; }
