分析
并查集是一种思想:
1.开始每个元素都是一个独立的集合(互异性)
2.通过根节点的编号表示集合(也可以加上集合的附加属性)
3.核心是查找函数,每次查找将路径上的元素全都指向根元素
C++ 代码
#include<iostream>
#include<cstring>
#include<cmath>
#include <vector>
#include<algorithm>
using namespace std;
#define ffor(i,begin,end) for(int i=(begin);i<(end);++i)//[begin,end)
#define out(x) cout<<x<<" "
#define nl cout<<endl
typedef long long LL;
const int INF = 1e9;
const int MAXN = 100010;
class UF{
public:
UF(int size){
for(int i=1;i<=size;i++){
father[i]=i;
}
}
int find(int goal){
if(father[goal]!=goal) father[goal]=find(father[goal]);
return father[goal];
}
void union2(int a,int b){
father[find(a)]=find(b);
}
private:
static const int N=100010;
int father[N];
};
//var
void AcWing(){
int n,m;
scanf("%d%d",&n,&m);
UF uf(n);
//循环内的输入输出就不要用cin cout了
while(m--){
char op[2];
int a,b;
scanf("%s%d%d",op,&a,&b);
if(op[0]<'Q'){
uf.union2(a,b);
}else{
uf.find(a)==uf.find(b) ? printf("Yes\n"):printf("No\n");
}
}
}
int main()
{
AcWing();
return 0;
}
兄弟有时间填个邀请码hhhhhhhhh(可以得AC币,邀请码在学生认证那填) 我的邀请码是:GUDFH