#include<bits/stdc++.h> using namespace std; int i,j,k,n,m,s,ans,f[10010],p1,p2,p3; //f[i]表示i的集合名 int find(int k){ //路径压缩 if(f[k]==k)return k; return f[k]=find(f[k]); } int main() { cin>>n>>m; for(i=1;i<=n;i++) f[i]=i;//初始化i的老大为自己 for(i=1;i<=m;i++){ cin>>p1>>p2>>p3; if(p1==1) f[find(p2)]=find(p3); //p3打赢了p2 else if(find(p2)==find(p3)) //是否是一伙的 printf("Y\n"); else printf("N\n"); } return 0; }

这是一个并查集的实现，用于解决集合合并和判断两个元素是否在同一个集合中的问题。其中，路径压缩和按秩合并这两个优化方法可以提高并查集的效率。

具体实现方法如下：
1. 初始化每个元素的集合名为自身。
2. 对于每个合并操作，找到两个元素所在的集合，将其中一个元素的集合名改为另一个元素的集合名，表示这两个元素属于同一个集合。
3. 对于每个查询操作，判断两个元素的集合名是否相同，若相同则输出 Y 表示在同一个集合中，否则输出 N 表示不在同一个集合中。

该实现中使用了路径压缩优化，即在查找集合名的过程中将遇到的所有元素的集合名都改为根节点的集合名，从而降低了后续查找的时间复杂度。