并查集

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 2e5 + 10;
 5 int n,m,x,y,z;
 6 int p[N]; //p[x] 是 x 点的祖先
 7 
 8 int find(int x)  // 并查集
 9 {
10     if (p[x] != x) p[x] = find(p[x]); //父亲不是自己就继续接着找
11     return p[x]; //返回祖先
12 }
13 
14 
15 int main ()
16 {
17     cin >> n >> m;
18     for (int i = 1; i <= n; i ++ ) p[i] = i;
19     
20     while (m -- )
21     {
22         cin >> z >> x >> y;
23         int a = find(x), b = find(y);
24         
25         if(z == 1) p[a] = b;//x点的祖先的爹记为y点的祖先
26         
27         if(z == 2) 
28         {
29             if(a == b) puts("Y"); // 爹一样就说明在一个集合里
30             else puts("N"); //爹不一样说明不在一个集合里
31         }
32     }
33     
34     return 0;
35 }