（好的期末考试考砸的我滚回来写代码来了TAT） （咦我什么时候期末考试考好过~~） 却说勇者有很多的亲戚，亲戚又有很多的亲戚，亲戚的亲戚就是自己的亲戚。 不幸的是，亲戚中有些人不是很有钱，所以说会管勇者借钱。 勇者丝毫不介意啊，毕竟自从他讨伐完大龙之后，他就日日有国王一个金币的俸禄。 可是，终有一天，勇者发现一天之内，亲戚就来了十多个。 还是路由器发现的，他将族谱整理完之后才告诉他说：“那些人有一半都不是你们家族的，就是过来诈骗的！” 勇者哑口无言，为了拯救自己的金币，他需要知道哪些人是自己的亲戚。
——————————————
输入格式： 第一行包含两个整数N、M，表示共有N个人和M次操作。 接下来M行，每行包含三个整数Zi、Xi、Yi 当Zi=1时，表示Xi与Yi是亲戚 当Zi=2时，输出Xi与Yi是否是亲戚，是的话输出Y；否则话输出N 输出格式： 如上，对于每一个Zi=2的操作，都有一行输出，每行包含一个大写字母，为Y或者N 提示： 亲戚的亲戚是亲戚
——————————————
（题外话） 好的，我们接下来就是要讲一个高深莫测玄幻之际的——并查集。 好吧在路由器没学之前一直以为并查集是huge佬所学的。 那么今天将带给蒟蒻也能看懂的并查集教程！ 首先让我们知道并查集的作用：简短点说，就是需要完成的任务有1.合并集合2.查询两个元素是否在同一个集合内。 上面那句话一定要看懂再往下看（不然你会和路由器一样当机半小时） 那么，让我们正式开始。
——————————————
勇者花费了一天的时间，终于找齐了所有七大姑八大姨了，那么接下来就是需要靠古老魔法的帮助来完成族谱了。 路由器也在照相馆中找到了魔法书，上面赫然写着三个字。 并查集。 “并查集的实现是类似于树一般，一整棵树代表了一整个集合。这样做的好处是，我们要想知道元素是否在同一个集合内，只需要看他们所在的集合的根节点是否一样即可。” “但是，这并非意味着图论，因为链式前向星有很大的空间限制。” “我们用一个很简单的方法实现建树——fa数组（指father，不要想象成奇怪的东西）” “fa数组的作用，fa[i]=j表示j是i的爸爸。规定根节点的爸爸为根节点。” “这样，当我们知道了要合并的两个元素i，j时，找到i与j的根节点if，jf，我们就可以简单粗暴的用fa[if]= jf来实现。” “那么就只有一个问题了，查询。” “查询方法：即不断递归，就是fa套fa套fa套fa……直到fa[i]=i，这时候我们就找到了所在集合的根节点了。” “然后比较这样得到的根节点即可，相等，即为一个集合……” 勇者“啪”的一声跑了出去，然后用自己的魔法代码功力敲完了魔法。 （但是这个魔法有缺陷，因此不贴出啦！实际上是懒~）
然而有一天，勇者气喘吁吁的找到了路由器。 “路由器，那个魔法……他，不管用了！” “啊？怎么回事？”路由器疑惑问道。 “额……我把这个魔法卖给了精灵族，但他们第二天就要求退货，说不灵了。” “不灵到不至于，怕不是太慢。”路由器懒洋洋地说，“那到底怎么回事啊？” “因为精灵能活千多岁……所以，”勇者支吾道，“他们将自己输入，再把爸爸输入，再爷爷，再太爷爷，再太太爷爷，再太太太爷爷，再……” “行了，我知道什么问题了，”路由器拜拜手，“你还是把书好好看看吧！” 勇者拿起书，将最后一点问题看完。 “……然而，有的时候，这样做出来的树实际上只有几个支链，有的甚至没有支链，那么找的速度就会明显增加。” “但是解决的办法也很简单——我们先查一遍，然后把所有沿途遇到的元素的爸爸（fa）全设为根节点即可。” “以下是本书附带魔法代码，如有不懂参看注释。”
#include<cstdio> #include<cstring> #include<iostream> #include<cmath> #include<algorithm> using namespace std; int fa[10001]={0}; int find(int a){//找到a所在的集合的根节点 if(fa[a]!=a)fa[a]=find(fa[a]); //路径压缩优化 //当我们找到根节点的时候 //我们将这一路上我们往上爬的所有的节点 //全部指向这个根节点，这样再搜就会很快 return fa[a]; //最开始的时候，我们碰到了第一个fa[a]==a //此时我们就知道了fa[a]为根节点 //将fa[a]的值传递给上一个fa[a]，完成路径压缩 //经过压缩之后到这个a，此时fa[a]就是根节点 } void judge(int a,int b){//判断是否在同一个集合里 if(find(a)!=find(b)){ printf("N\n"); }else{ printf("Y\n"); } return; } void unionn(int a,int b){//合并以a，b为*根节点*与的两个集合 fa[b]=a;//简单粗暴的将两棵树连接起来 return; } int main(){ int n,m;//N个元素和M个操作 scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ fa[i]=i; //初始化，将每一个集合视为一棵树 //则开始时对于每一个元素，他的根节点就是他本身 } for(int i=1;i<=m;i++){ int a1,b1,a,b,z; scanf("%d%d%d",&z,&a,&b); if(z==1){ a1=find(a); b1=find(b); if(a1!=b1){//不是同一个集合 unionn(a1,b1); } }else{ judge(a,b); } } return 0; }下面附带模板题： 洛谷 P3367 【模板】并查集：https://www.luogu.org/problem/show?pid=3367#sub 真的是模板，你只需要将上面的程序复制粘贴就AC啦！
