公司要建设网站需要那些程序建网站浩森宇特
合并集合
-
核心思想:并查集:
- 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;}}}
-