2.数据结构：3.合并集合

原题链接

#include<algorithm> #include<cstring> #include<iostream> using namespace std; const int N=100010; int p[N]; int find(int x){ if(p[x]!=x){ p[x]=find(p[x]); } return p[x]; } int main(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++){ p[i]=i; } while(m--){ char op[2]; int a,b; cin>>op>>a>>b; if(op[0]=='M'){ if(find(p[a])!=find(p[b])){ p[find(a)]=find(b); } }else{ if(find(a)==find(b)){ puts("Yes"); }else{ puts("No"); } } } return 0; }

维护每个点的根节点，合并是修改根节点，查询也是比较根节点。