算法基础之合并集合

合并集合

• 核心思想:并查集:

  • 1.将两个集合合并
  • 2.询问两个元素是否在一个集合当中

• 基本原理:每个集合用一棵树表示 树根的编号就是整个集合的编号
  每个节点存储其父节点，p[x]表示x的父节点

  • 

  •   #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--){string op;int a,b;cin>>op>>a>>b;if(op=="M") p[find(a)] = find(b);  //合并操作 将a的父节点改为belse{if(find(a) == find(b)) cout<<"Yes"<<endl;else cout<<"No"<<endl;}}}