1 solutions
-
0
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