合并集合

• 核心思想:并查集:

  • 1.將兩個集合合并
  • 2.詢問兩個元素是否在一個集合當(dāng)中

• 基本原理:每個集合用一棵樹表示 樹根的編號就是整個集合的編號
  每個節(jié)點(diǎn)存儲其父節(jié)點(diǎn)，p[x]表示x的父節(jié)點(diǎn)

  • 

  •   #include<iostream>using namespace std;const int N=100010;int p[N];//路徑壓縮優(yōu)化后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的父節(jié)點(diǎn)改為belse{if(find(a) == find(b)) cout<<"Yes"<<endl;else cout<<"No"<<endl;}}}