4 solutions

  • 4
    @ 2022-1-6 14:33:57
    #include<iostream>
    using  namespace std;
    const int N=5e3+7;
    int f[N];
    
    //初始化每个人的祖先都是自己
    void init(){
    	for(int i=1;i<N;i++)
    		f[i]=i;
    }
    
    //查找x的祖先
    int fin(int x){
    	while(x!=f[x])
    		x=f[x];
    	return x;
    }
    
    //合并两个人的祖先
    void merge(int a,int b){
    	a=fin(a);
    	b=fin(b);
    	f[b]=a;
    }
    
    int main(){
    	init();
    	int n,p,m;
    	cin>>n>>m>>p;
    
    	//构建亲戚关系
    	for(int i=1;i<=m;i++){
    		int a,b;
    		cin>>a>>b;
    		merge(a,b);
    	}
    
    	//开始询问
    	while(p--){
    		int a,b;
    		cin>>a>>b;
    		if(fin(a)==fin(b))
    			cout<<"Yes"<<endl;
    			else cout<<"No"<<endl;
    	}
    	
    	return 0;
    }
    
    • 2
      @ 2022-4-6 16:06:14
      #include<iostream>
      #include<vector>
      #include<stack>
      using namespace std;
      static const int MAX = 10007;
      static const int NIL = -1;
      
      //使用vector实现邻接表
      int n;
      vector<int>G[MAX];
      int color[MAX];
      
      //深搜实现连通图的染色
      void dfs(int r,int c){
      	stack<int>S;
      	S.push(r);
      	color[r]=c;
      	while(!S.empty()){
      		int u=S.top();S.pop();
      		for(int i=0;i<G[u].size();i++){
      			int v=G[u][i];
      			if(color[v]==NIL){
      				color[v]=c;
      				S.push(v);
      			}
      		}
      	}
      }
      
      //遍历图,逐个染色
      void assignColor(){
      	int id=1;
      	for(int i=0;i<=n;i++)color[i]=NIL;
      	for(int i=0;i<=n;i++){
      		if(color[i]==NIL)dfs(i,id++);
      	}
      }
      
      int main(){
      	int s,t,m,q;
      	
      	cin>>n>>m>>q;
      	
      	for(int i=0;i<m;i++){
      		cin>>s>>t;
      		G[s].push_back(t);
      		G[t].push_back(s);
      	}
      	
      	assignColor();
      	
      	for(int i=0;i<q;i++){
      		cin>>s>>t;
      		if(color[s]==color[t])cout<<"Yes"<<endl;
      		else cout<<"No"<<endl;
      	}
      	
      	return 0;
      }
      
      • 1
        @ 2022-1-8 17:25:17
        #include <bits/stdc++.h>
        using namespace std;
        int w[5007];
        int find(int x){//找祖先
        	if(w[x]==x) return x;
        	return w[x]=find(w[x]);//关键点:让每个人都直接指向自己的祖先,便于快速查找
        }
        int main(){
        	int n,m,p,x,y;
        	cin>>n>>m>>p;
        	for(int i=1;i<n;i++) w[i]=i;//自己为自己祖先
        	for(int i=0;i<m;i++){
        		cin>>x>>y;
        		w[find(x)]=find(y);//添加关系
        	}
        	for(int i=0;i<p;i++){//判断
        		cin>>x>>y;
        		if(find(x)==find(y)) cout<<"Yes"<<endl;
        		else cout<<"No"<<endl;
        	}
        	return 0;
        } 
        
        • 0
          @ 2022-4-5 17:50:05
          n, m, p = map(int, input().split())
          f = [i for i in range(n+1)] 
          def find(x):
              if(f[x]!=x):  f[x] = find(f[x])
              return f[x]
          def union(a, b):
              a = find(a)
              b = find(b)
              if(a != b):  f[a] = b
          for _ in range(m):
              a, b = map(int, input().split())
              union(a, b)
          for _ in range(p):
              i, j = map(int, input().split())
              print("Yes" if find(i)==find(j) else "No")
          
          • 1

          Information

          ID
          1257
          Time
          1000ms
          Memory
          128MiB
          Difficulty
          4
          Tags
          # Submissions
          141
          Accepted
          66
          Uploaded By