1 solutions

  • 0
    @ 2025-3-3 16:21:27

    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