数据结构——并查集

AcWing - 算法基础课

Acwing——合并集合

代码如下：

#include <bits/stdc++.h>using namespace std;
#define fs first
#define sc second
#define endl '\n'
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef pair<int, int> PII;const int N = 1e5+10;int p[N];int find(int x)
{if(x==p[x])return x;//找到根了x==p[x]//否则压缩路径 把节点直接指向老祖宗(优化)else p[x]=find(p[x]);
}void solve(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++)p[i]=i;//初始化(每个人都是自己的祖宗)for(int i=0;i<m;i++){char x;cin>>x;int a,b;if(x=='M'){cin>>a>>b;p[find(a)]=find(b);//两个集合合并}else{cin>>a>>b;if(find(a)==find(b))puts("Yes");else puts("No");}}
}int main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t;t=1;while (t--){solve();}return 0;
}