P3367 并查集 模板题

P3367 并查集 模板题

🔗 原题链接
📌 标题形貌

标题

现在有 \(n\) 个元素，分为多少个聚集。须要支持两种操纵：

• 归并操纵 (\(z=1\))：将 \(x\) 和 \(y\) 地点的聚集归并为一个聚集
  
• 查询操纵 (\(z=2\))：查询 \(x\) 和 \(y\) 是否在同一个聚会合
  

输入格式

• 第一行：\(n, m\)（\(n\) 个元素，\(m\) 次操纵）
  
• 接下来 \(m\) 行：每行三个整数 \(z, x, y\)
  
  
  
  • 若 \(z=1\)：归并 \(x, y\) 地点聚集
    
  • 若 \(z=2\)：查询 \(x, y\) 是否同属一个聚集
    
  
  

输特别式

• 对每个查询操纵（\(z=2\)），输出 Y 或 N
  

束缚条件

• \(1 \leq n \leq 10^5\)
  
• \(1 \leq m \leq 10^5\)
  
• \(1 \leq x, y \leq n\)
  

💡 焦点思绪

1. 每个点都是一颗树的节点，
2. 相同集合的点的根相同，
3. 指向同一个数
5. 并查集 = 树结构 + 找根（find） + 合并（union） + 路径压缩优化

复制代码

📋 模板步调

1. 初始化树

复制代码

1.    rep(i,1,n+1) fa[i]=i;//每个节点的fa都是自己
3.     每个循环输入x,y
4.     先找到他们各自的根
6.     x=find(x),y=find(y);
7.     如果合并，把y的根节点指向x的根节点，
8.     x=fa[y];
9.     否则判断两者的根是否相同
10.    
11.     找根节点find函数实现
12. ##  优化点
13.     使用递归可将沿路的的节点的父节点都指向根节点，
14.     使树的深度接近常数级，提升后续查询效率
16.     int find(int x){
17.         if(fa[x]==x) return x;
18.         return fa[x]=find(fa[x]);
19.     }

复制代码

代码实现

完备代码

[code]    const int N=2e5+5;    int a[N];        int find(int x){        if(x==fa[x]) return x;        return fa[x]=find(fa[x]);    }    void solve(){        int n,m;        cin>>n>>m;        rep(i,1,n+1) fa=i;            int x,y,z;        while(m--){            cin>>z;            x=find(x);            y=find(y);            if(z==1){                x=fa[y];            }            else {                if(x==y) cout