/ Vijos / 题库 / 家族 /

题解

282 条题解

  • -1
    @ 2016-11-23 15:27:54

    论定义rank数组对1A的影响orzzz

    #include<iostream>
    using namespace std;
    int n,m,p;
    int par[5005],ran[5005];

    void init(int q){
    for(int i=1;i<=q;i++){
    par[i]=i;
    ran[i]=0;
    }
    }

    int find(int x){
    if(par[x]==x) return x;
    else return par[x]=find(par[x]);
    }

    void unite(int a,int b){
    a=find(a);
    b=find(b);
    if(a==b) return;
    if(ran[a]<ran[b]) par[a]=b;
    else{
    par[b]=a;
    if(ran[a]==ran[b]) ran[a]++;
    }
    }

    bool same(int x,int y){
    return find(x)==find(y);
    }

    int main(){
    cin>>n>>m>>p;
    init(n);
    int res1,res2;
    for(int i=1;i<=m;i++){
    cin>>res1>>res2;
    unite(res1,res2);
    }
    for(int i=1;i<=p;i++){
    cin>>res1>>res2;
    if(same(res1,res2)==true) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    }
    return 0;
    }

  • -1
    @ 2016-11-19 15:25:11

    裸的并查集,瑟瑟发抖
    program exx(input,output);
    var
    n,m,p,i,x,y:longint;
    fa:array[1..5000] of longint;
    function gf(x:longint):longint;
    begin
    if fa[x]=x then exit(x);
    fa[x]:=gf(fa[x]);
    exit(fa[x]);
    end;

    procedure union(x,y:longint);
    var
    xx,yy:longint;
    begin
    xx:=gf(x);
    yy:=gf(y);
    fa[xx]:=yy;
    end;
    function ask(x,y:longint):boolean;
    begin
    if gf(x)=gf(y) then exit(true) else exit(false);
    end;
    begin
    readln(n,m,p);
    for i:=1 to n do
    fa[i]:=i;
    for i:=1 to m do
    begin
    readln(X,y);
    union(x,y);
    end;
    for i:=1 to p do
    begin
    readln(x,y);
    if ask(x,y) then writeln('Yes') else writeln('No');
    end;
    end.

信息

ID
1034
难度
4
分类
数据结构 | 并查集 点击显示
标签
(无)
递交数
9368
已通过
3839
通过率
41%
被复制
15
上传者