1 solutions
-
0
C++ :
#include<bits/stdc++.h> using namespace std; int n,m,p,f[5100],c,d,a,b; //找到元素x的根(不含路径压缩) int find(int x){ //如果x的父节点就是自己,那么x就是根,否则找f[x]的根 return f[x]==x?x:find(f[x]); //路径压缩版本的写法 //如果x的父节点就是自己,那么x就是根,否则将x的父节点直接指向x所在集合的根 //return f[x]==x?x:f[x]=find(f[x]); } //合并:将x和y合并到同一个集合 void merge(int x,int y){ //将y的根的父节点,设置为x的根 f[find(y)] = find(x); } int main() { //n个人,m个亲戚关系,p次查询 cin>>n>>m>>p; //初始化,每个人的根节点都指向自己 for(int i = 1;i <= n;i++){ f[i] = i; } for(int i = 1;i <= m;i++){ cin>>c>>d; //cd是亲戚关系,将其合并到同一个集合 merge(c,d); } //p次查询 for(int i = 1;i <= p;i++){ cin>>a>>b; //问:ab是否有亲戚关系,如果ab的根节点相同,那么是亲戚 if(find(a)==find(b)){ cout<<"Yes"<<endl; } else{ cout<<"No"<<endl; } } return 0; }
- 1
Information
- ID
- 9963
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- (None)
- Tags
- # Submissions
- 0
- Accepted
- 0
- Uploaded By