//给大家小总结一下并查集 #include<bits/stdc++.h> using namespace std; #define int long long // 并查集---解决连通块问题--集合（无重复） 1 如其名 1>并：合并俩集合 2>查: 查看俩元素是不是在一个集合中 2 主要衍生问题 1>所有连通块问题-- 几个连通块 是否整体联通 带权连通块等 2>了解 kruskal算法求最小生成树时--不能成环 判断 3 思想---抽象到具体 1>用树(边数最小图)存 即 p[x]=y; p[子]=父；x--->y 2> 初始化-- 开始每个点依次编号1-n 此时每个点都是根节点 即单独集合 3> 并 通过p[子]=父 所以不断吞并产生大集合(树存)---此时注意仅最大父节点没有被并化 所以唯一 p[x]=x; 此时通过x来唯一标记集合 4> 查 所以 1>俩点是否在一个集合 看他们的集合编号（根本父节点）是否相同 2>有几个连通块---看有几个集合编号 即 p[x]=x的个数 5>对查的优化---压缩路径 此时 并查集简单操作时间还是太大 主要以为在查找根本根时 x-->y-->z-->w...... 还是太大了 因为我们根本只需要查祖先而不在于他们内部其他父子关系 所以----每次查时 1对祖先节点--直接返回 2对非祖先节点--父亲变祖先 之后对本次集合查询就优化到 几乎O(1)---实际O(log(logn))

0:初始化： p[i]=i; 1并： p[find(a)]=find(b) 2查：if(find(a)find(b))
*/ // 并查集重在查 //int find(int x)//返回x的祖先并顺手压缩路径 //{ // if(p[x]!=x)p[x]=find(p[x]);//不是祖先就压缩 // return p[x]; //是祖先就返回 //} const int N=1e5+5; int p[N];//p[子]=父 int n,k; //最重要的 find--找先人函数--先人;p[x]=x; int find(int x) { if(p[x]!=x) p[x]=find(p[x]);//往上找并更新 return p[x]; } signed main() { std::ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>k; char op;//M a,b合并 //Q a,b 查是不是在一起 int a,b; for(int i=1;i<=n;i++) p[i]=i;//1初始化 while(k--) { cin>>op>>a>>b; if(op'M') p[find(a)]=find(b);//我先人人你先人当爸爸 else { if(find(a)==find(b)) cout<<"Yes"<<"\n"; else cout<<"No"<<"\n"; } } return 0; }