并查集,
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 1e5 + 10; int a,b,n,m; int p[N];//记录每一个点的父节点 //这里后来会用到路径压缩,这样的话得到的就是他的根节点,也就是祖宗节点 int find(int x){ if(p[x] != x) p[x] = find(p[x]);//如果当前这个数不等于他的父节点,那就继续找他的父节点的父节点 return p[x]; //最后返回的一定是根节点,也就是祖宗节点 } int main(){ cin >> n >> m ; for(int i = 1 ; i <= n ; i ++ ) p[i] = i ; while(m -- ){ char c[2]; scanf("%s%d%d",&c,&a,&b); if(*c == 'M') p[find(a)] = find(b);//如果想合并两个集合,那就让a的祖宗节点变成b的祖宗节点 else { if(find(a) == find(b)) { cout << "Yes" << endl ; }else { cout << "No" << endl ; } } } return 0; }