查询两个元素是否属于同一类
比较形象的是亲戚，A是B的爸爸，B是C的爸爸，问A与C是否有关系；
也可以是城市道路，有1，2，3这三个城市，有道路1 - 2，2 - 3，问1城市能否到达3城市；
第一行包含两个整数N、M，表示共有N个元素和M个操作。
接下来M行，每行包含三个整数Zi、Xi、Yi
当Zi=1时，将Xi与Yi所在的集合合并
当Zi=2时，输出Xi与Yi是否在同一集合内，是的话输出Y；否则话输出N；
4 7 2 1 2 1 1 2 2 1 2 1 3 4 2 1 4 1 2 3 2 1 4
#include <bits/stdc++.h> using namespace std; const int N = 100001; int n,m; int fa[N]; int find(int x){ return fa[x] == x ? x : find(fa[x]); } void uni(int x, int y){ fa[find(x)] = find(y); } int ask(int x, int y){ return find(x) == find(y); } int main(){ cin >> n >> m; for(int i = 1; i <= n; ++i) fa[i] = i; // 最开始只和自己有关系 for(int i = 1, x, y, z; i <= m; ++i){ cin >> z >> x >> y; if(z == 1) uni(x, y); else ask(x, y) == true ? printf("Y\n") : printf("N\n"); } return 0; }
如果我们只考虑他们祖先，不考虑各个之间的具体关系，就可以在find函数里加个优化
int find(int x){ return fa[x] == x ? x : fa[x] = find(fa[x]); }
原文：https://www.cnblogs.com/Adventurer-H/p/11224896.html