1 solutions

  • 0
    @ 2024-12-10 23:09:38

    C :

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define maxn 20010
    
    int f[20010];
    int n, m;
    
    int find(int v){
    if(f[v] == v)return v;
    int F = find(f[v]);
    f[v] = F;
    return F;
    }
    
    int main()
    {
        while(scanf("%d%d",&n,&m) != EOF){
            for(int i = 1;i <= n; i++)f[i] = i;
            for(int i = 0;i < m; i++){
                int a, b;
                scanf("%d%d",&a,&b);
                int fa = find(a);
                int fb = find(b);
                f[fb] = fa;
            }
            int Q;
            scanf("%d",&Q);
            while(Q--){
                int a, b;
                scanf("%d%d",&a,&b);
                int fa = find(a);
                int fb = find(b);
                if(fa==fb){
                    printf("Yes\n");
                }
                else{
                    printf("No\n");
                }
            }
        }
        return 0;
    }
    

    C++ :

    #include<iostream>
    #include<cstring>
    using namespace std;
    int father[200010];
    int n,m,q;
    int getfather(int);
    void merge(int,int);
    bool judge(int,int);
    void work();
    int main()
    {
    	work();
    	return 0;
    }
    void work()
    {
    	cin>>n>>m;
    	for(int i=1;i<=n;i++)father[i]=i;
    	int x,y;
    	for(int i=1;i<=m;i++)
    	{
    		cin>>x>>y;
    		merge(x,y);
    	}
    	int q;
    	cin>>q;
    	for(int i=1;i<=q;i++)
    	{
    		cin>>x>>y;
    		if(judge(x,y))cout<<"Yes"<<endl;
    		else cout<<"No"<<endl;
    	}
    }
    int getfather(int x)
    {
    	if(father[x]==x)return x;
    	father[x]=getfather(father[x]);
    	return father[x];
    }
    void merge(int x,int y)
    {
    	x=getfather(x);
    	y=getfather(y);
    	father[x]=y;
    }
    bool judge(int x,int y)
    {
    	x=getfather(x);
    	y=getfather(y);
    	if(x==y)return 1;
    	else return 0;
    }
    

    Pascal :

    var
      n,m,i,x,y:longint;
      f:array[0..100000] of longint;
    
    function find(x:longint):longint;
      begin
        if f[x]=x then exit(x);
        f[x]:=find(f[x]);
        exit(f[x]);
      end;
    
    procedure combine(x,y:longint);
      var
        xx,yy:longint;
      begin
        xx:=find(x);
        yy:=find(y);
        if xx<>yy then f[xx]:=yy;
      end;
    
    begin
      readln(n,m);
      for i:=1 to n do
        f[i]:=i;
      for i:=1 to m do
        begin
          readln(x,y);
          combine(x,y);
        end;
      readln(m);
      for i:=1 to m do
        begin
          readln(x,y);
          if find(x)=find(y) then writeln('Yes')
            else writeln('No');
        end;
    
    end.
    
    

    Java :

    
    
    import java.util.Scanner;
    
    public class Main{
    	static int n,m,t;
    	static int []pre;
    	static void init(int m) {
    		pre=new int[m+1];
    		for(int i=0;i<=m;i++) {
    			pre[i]=i;
    		}
    	}
    	static int find(int x) {
    		if(pre[x]==x) return x;
    		return pre[x]=find(pre[x]);
    	}
    	static void merge(int x,int y) {
    		int fx=find(x);
    		int fy=find(y);
    		if(fx==fy) return;
    		pre[fx]=fy;
    	}
    	public static void main(String[]args) {
    		Scanner sc=new Scanner(System.in);
    		n=sc.nextInt();
    		m=sc.nextInt();
    		init(n);
    		for(int i=0;i<m;i++) {
    			int a1=sc.nextInt();
    			int a2=sc.nextInt();
    			merge(a1, a2);
    		}
    		t=sc.nextInt();
    		for(int i=0;i<t;i++) {
    		 int b1=sc.nextInt();
    		 int b2=sc.nextInt();
    		 if(find(b2)==find(b1))System.out.println("Yes");
    		 else System.out.println("No");
    		}
    	}
    }
    
    • 1

    Information

    ID
    583
    Time
    2000ms
    Memory
    128MiB
    Difficulty
    (None)
    Tags
    # Submissions
    0
    Accepted
    0
    Uploaded By