并查集 - ## 并查集

Description

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

---

Input

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

接下来 \(M\) 行，每行包含三个整数 \(Z_i, X_i, Y_i\)：

• 当 \(Z_i = 1\) 时，将 \(X_i\) 与 \(Y_i\) 所在的集合合并。
• 当 \(Z_i = 2\) 时，输出 \(X_i\) 与 \(Y_i\) 是否在同一集合内：
  • 如果是，输出 Y
  • 否则输出 N

---

Output

对于每一个 \(Z_i = 2\) 的操作，输出一行，每行包含一个大写字母，为 Y 或者 N。

---

Sample

Input

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

Output

N
Y
N
Y

---

数据范围

• \(1 \leq N \leq 2 \times 10^5\)
• \(1 \leq M \leq 10^6\)
• \(1 \leq X_i, Y_i \leq N\)
• \(Z_i \in \{1, 2\}\)

---

#include <bits/stdc++.h>
using namespace std;
int n,m,Fa[200005];
int GetFa(int k) {if (k==Fa[k]) return k;return Fa[k]=GetFa(Fa[k]);
}
void Merge(int x,int y) {int fx=GetFa(x);int fy=GetFa(y);if (fx!=fy) Fa[fy]=fx;
}
int main(){cin>>n>>m;for (int i=1;i<=n;i++) Fa[i]=i;for (int i=1;i<=m;i++) {int z,x,y;cin>>z>>x>>y;if (z==1) Merge(x,y);if (z==2) {if (GetFa(x)!=GetFa(y)) cout<<"N\n";else cout<<"Y\n";}}return 0;
}