/ Vijos / 题库 / 家族 /

题解

282 条题解

  • 0
    @ 2015-03-24 16:37:18

    program org;
    var
    x,i,j,m,n,a,b,p:longint;
    fa:array[1..5000] of longint;

    function find(x:longint):longint;
    begin
    if x=fa[x] then exit(x);
    fa[x]:=find(fa[x]);
    exit(fa[x]);
    end;
    begin
    read(n,m,p);
    for i:=1 to n do fa[i]:=i;
    for i:=1 to m do begin read(a,b);
    fa[find(a)]:=find(b);
    end;
    for i:=1 to p do begin read(a,b);
    if fa[a]=fa[b] then writeln('yes') else writeln('no');end;
    for i:=1 to n do writeln(fa[i]);
    end.

  • 0
    @ 2015-03-03 17:34:12

    #include<iostream>
    #include<string>
    using namespace std;
    int n,m,x,y,q,father[10000];
    string s[5005];
    int find(int x)
    {
    if(father[x]!=x) father[x]=find(father[x]);
    return father[x];
    }
    void link(int x,int y)
    {
    father[y]=x;
    }
    int main()
    {
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
    father[i]=i;
    for(int i=1;i<=m;i++)
    {
    cin>>x>>y;
    int l1=find(x);
    int l2=find(y);
    if(l1!=l2) link(l1,l2);
    }
    for(int i=1;i<=q;i++)
    {
    cin>>x>>y;
    if(find(x)==find(y)) s[i]="Yes";
    else
    s[i]="No";
    }
    for(int i=1;i<=q;i++)
    cout<<s[i]<<endl;
    }

  • 0
    @ 2015-02-23 12:22:48

    并查集,采用了路径压缩,可以阅读关于并查集的资料以帮助理解代码

    Pascal Code

    var
    father:array[1..5000] of longint; //father数组存储顶点的上级之一
    n,m,p,i,t1,t2:longint;
    function find(x:longint):longint;
    begin
    if x=father[x] then exit(x);
    father[x]:=find(father[x]); //路径压缩
    exit(father[x]);
    end;
    procedure merge(x,y:longint);
    begin
    father[find(x)]:=find(y); //令y的父亲成为x的父亲的上级
    end;
    begin
    readln(n,m,p);
    for i:=1 to n do
    father[i]:=i;
    for i:=1 to m do
    begin
    readln(t1,t2);
    merge(t1,t2);
    end;
    for i:=1 to p do
    begin
    readln(t1,t2);
    if find(t1)=find(t2) then writeln('Yes')
    else writeln('No');
    end;
    end.

  • 0
    @ 2015-01-09 17:35:25

    哈,原来这就是并查集,看了下书就会啦,一遍AC,继续练去喽~
    ###Block code

    program ex;
    var fa:array[1..5000] of longint;
    i,j,n,m,p,k1,k2:longint;
    ans:string;
    function father(x:longint):longint;
    begin
    if fa[x]=x then
    exit(x);
    fa[x]:=father(fa[x]); exit(fa[x]);
    end;

    procedure add(a,b:longint);
    var f1,f2:longint;
    begin
    f1:=father(a); f2:=father(b); fa[f2]:=f1;
    end;

    function search(a1,a2:longint):string;
    begin
    if father(a1)=father(a2) then
    exit('Yes')
    else
    exit('No');
    end;

    begin //main
    read(n,m,p);
    for i:=1 to n do fa[i]:=i;

    for i:=1 to m do begin
    read(k1,k2); add(k1,k2);
    end;

    for i:=1 to p do begin
    read(k1,k2); ans:=search(k1,k2); writeln(ans);
    end;

    end.

  • 0
    @ 2014-11-07 22:54:25

    var f:array[1..5010]of longint;
    n,m,p:longint;
    function father(v:longint):longint;
    begin
    if f[v]=v then exit(v);
    f[v]:=father(f[v]);
    exit(f[v]);
    end;

    procedure add(x,y:longint);
    var fx,fy:longint;
    begin
    fx:=father(x);
    fy:=father(y);
    if fx<>fy then f[fx]:=fy;
    end;

    procedure init;
    var i,j,x,y:longint;
    begin
    readln(n,m,p);
    for i:=1 to n do f[i]:=i;
    for i:=1 to m do
    begin
    readln(x,y);
    add(x,y);
    end;
    for i:=1 to p do
    begin
    readln(x,y);
    if father(x)=father(y) then writeln('Yes')
    else
    writeln('No');
    end;
    end;

    begin
    init;
    end.

  • 0
    @ 2014-11-05 22:35:35

    var i,j,n,m,p,a,b,l:longint;
    x:array[0..6001] of longint;
    gx:array[0..8000,0..8000] of boolean;
    begin
    readln(n,m,p);
    for i:=1 to n do
    for j:=1 to n do
    gx[i,j]:=false;
    for i:=1 to m do
    begin
    readln(a,b);
    gx[a,b]:=true;
    gx[b,a]:=true;
    end;
    for i:=1 to n do
    x[i]:=i;
    for l:=1 to 8 do
    for i:=1 to n do
    for j:=1 to n do
    if (gx[i,j]) and (x[j]>x[i]) then
    x[j]:=x[i]
    else if (gx[i,j]) then x[i]:=x[j];
    for i:=1 to p do
    begin
    readln(a,b);
    if x[a]=x[b] then writeln('Yes')
    else writeln('No');
    end;
    end.
    为什么都用并查集??

  • 0
    @ 2014-10-30 19:17:19

    #include<iostream>
    #include<cstdio>
    using namespace std;
    const int maxb=5005;
    int numd,numb,numq;
    int fa[maxb];
    struct m
    {
    int x;

    int y;
    };m k[maxb];
    int get(int x)
    {
    int root=x;
    while(root!=fa[root])
    root=fa[root];
    while(x!=root)
    {
    int tfa=fa[x];
    fa[x]=root;
    x=tfa;

    }
    return root;

    }
    int main()
    {
    int a,b;
    scanf("%d%d%d",&numd,&numb,&numq);

    for(int i=1;i<=numd;i++)
    fa[i]=i;
    for(int i=1;i<=numb;i++)
    {
    scanf("%d%d",&k[i].x,&k[i].y);

    fa[get(k[i].x)]=get(k[i].y);
    }
    for(int i=1;i<=numq;i++)
    {
    int a,b;
    scanf("%d%d",&a,&b);
    if(get(a)==get(b))
    printf("Yes\n");
    else
    printf("No\n");
    }

    return 0;

    }
    没看清大小写。。。

  • 0
    @ 2014-10-25 10:52:48

    var
    a:array[1..5000]of longint;
    s:array[1..5000]of string;
    m,n,p,i,x,y:longint;
    function findfather(x:longint):longint;
    begin
    if a[x]<>x then
    findfather:=findfather(a[x])
    else
    findfather:=a[x];
    end;
    begin
    readln(n,m,p);
    for i:=1 to n do
    a[i]:=i;
    for i:=1 to m do
    begin
    readln(x,y);
    x:=findfather(x);
    a[x]:=findfather(y);
    end;
    for i:=1 to n do
    a[i]:=findfather(i);
    for i:=1 to p do
    begin
    readln(x,y);
    if a[x]<>a[y] then
    s[i]:='No'
    else
    s[i]:='Yes';
    end;
    for i:=1 to p do
    writeln(s[i]);
    end.

  • 0
    @ 2014-10-24 10:39:01

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 828 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 832 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 832 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 828 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 832 KiB, score = 10
    测试数据 #5: Accepted, time = 15 ms, mem = 832 KiB, score = 10
    测试数据 #6: Accepted, time = 7 ms, mem = 828 KiB, score = 10
    测试数据 #7: Accepted, time = 15 ms, mem = 832 KiB, score = 10
    测试数据 #8: Accepted, time = 15 ms, mem = 832 KiB, score = 10
    测试数据 #9: Accepted, time = 15 ms, mem = 832 KiB, score = 10
    Accepted, time = 67 ms, mem = 832 KiB, score = 100
    ####代码
    program family;
    var
    father:array[1..5000] of integer;
    n,m,p,i,a,b:integer;
    function getfather(v:integer):integer;
    begin
    if father[v]=v then exit(v);
    father[v]:=getfather(father[v]);
    getfather:=father[v];
    end;
    procedure merge(x,y:integer);
    begin
    x:=getfather(x);
    y:=getfather(y);
    father[x]:=y;
    end;
    function judge(x,y:integer):boolean;
    begin
    x:=getfather(x);
    y:=getfather(y);
    exit(x=y);
    end;
    begin
    readln(n,m,p);
    for i:=1 to n do father[i]:=i;
    for i:=1 to m do
    begin
    readln(a,b);
    if not judge(a,b) then merge(a,b);
    end;
    for i:=1 to p do
    begin
    readln(a,b);
    if judge(a,b) then writeln('Yes') else writeln('No');
    end;
    readln;
    end.
    并查集。
    一定要审题!注意**大小写**!

  • 0
    @ 2014-10-20 12:17:12

    P1034 家族
    解题报告:
    很明显这道题用到的是并查集,而且是并查集的模板题。
    不需要任何变化,。首先使每个人形成一个独立的集合;
    对于读入的m对关系,查询他们是否属于一个集合,不属于就合并;
    对于读入的p个查询x,y,只要判断find(x)== f ind(y)?;
    如果等于就输出“Yes”, 反之输出“No”即可。

  • 0
    @ 2014-10-03 15:17:04

    #include<iostream>
    using namespace std;
    int f[5001];
    int find(int x)
    {
    if(f[x]!=x)
    f[x]=find(f[x]);
    return f[x];
    }
    main()
    {
    int n,m,p,i,x,y,a,b;
    cin>>n>>m>>p;
    for(i=1;i<=n;i++)
    f[i]=i;
    for(i=1;i<=m;i++)
    {
    cin>>x>>y;
    a=find(x);
    b=find(y);
    if(a!=b)
    f[b]=a;
    }
    for(i=1;i<=p;i++)
    {
    cin>>x>>y;
    if(find(x)==find(y))
    cout<<"Yes\n";
    else
    cout<<"No\n";
    }
    }

  • 0
    @ 2014-09-27 20:42:29

    评测结果
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 516 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 512 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 516 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 516 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 516 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 512 KiB, score = 10
    测试数据 #6: Accepted, time = 7 ms, mem = 512 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 516 KiB, score = 10
    测试数据 #8: Accepted, time = 7 ms, mem = 516 KiB, score = 10
    测试数据 #9: Accepted, time = 15 ms, mem = 516 KiB, score = 10
    Accepted, time = 29 ms, mem = 516 KiB, score = 100

    #include<cstdio>
    using namespace std;
    int n,m,p,parent[5005],fam[5000];
    int find(int x)
    {
    if(parent[x]==x) return x;
    parent[x]=find(parent[x]);
    return parent[x];
    }
    int main()
    {
    scanf("%d%d%d",&n,&m,&p);
    for(int i=1;i<=n;i++){
    parent[i]=i;
    }
    for(int i=1;i<=m;i++){
    int a,b;
    scanf("%d%d",&a,&b);
    int a1=find(a),b1=find(b);
    parent[a1]=b1;
    }
    for(int i=1;i<=p;i++){
    int c1,c2;
    scanf("%d%d",&c1,&c2);
    if ( find(c1)==find(c2) ) printf("Yes\n");else printf("No\n");
    }
    return 0;
    }

  • 0
    @ 2014-07-11 08:25:40

    #include<cstdio>
    int n,m,p;
    int id[5002]={0};
    inline void link(int x,int y);
    inline int find(int x);
    int main(){
    scanf("%d %d %d\n",&n,&m,&p);
    for(int i=1;i<=n;i++)id[i]=i;
    for(int i=0;i<m;i++){
    int x,y;
    scanf("%d %d\n",&x,&y);
    link(x,y);
    }
    for(int i=0;i<p;i++){
    int x,y;
    scanf("%d %d\n",&x,&y);
    if(find(x)==find(y)){
    printf("Yes\n");
    }else printf("No\n");
    }
    }
    inline void link(int x,int y){
    int xroot=find(x),yroot=find(y);
    id[yroot]=xroot;
    }
    inline int find(int x){
    while(id[x]!=x){
    x=id[x];
    }
    return x;
    }
    写得有点丑,没加路径压缩,用了75ms,压缩后更快

  • 0
    @ 2014-04-04 23:11:37

    就过了两个点,求大神解惑……
    #include<iostream>
    using namespace std;
    const int MAXN=5011;
    int a[MAXN];
    int main(){
    int i,n,m,p,x,y;
    int rele(int);
    cin>>n>>m>>p;
    for(i=1;i<=n;i++)a[i]=i;
    for(i=1;i<=m;i++){
    cin>>x>>y;
    if(x>y)a[x]=a[y];
    else a[y]=a[x];
    }
    for(i=1;i<=p;i++){
    cin>>x>>y;
    if(rele(x)==rele(y))cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    }
    return 0;
    }
    int rele(int x){
    if(a[x]==x)return x;
    else return rele(a[x]);
    }

  • 0
    @ 2014-03-22 21:21:54

    弱弱的题目,最简单的并查集,代码略丑,望请原谅
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    const int N=5001;
    int t[N],n,m,p,i;
    int findR(int x){
    if(t[x]==-1)return x;
    else return findR(t[x]);
    }
    void mergeR(int x,int y){
    int X=findR(x);
    int Y=findR(y);
    if(X!=Y)t[X]=Y;
    }
    void findans(int x,int y){
    int X=findR(x);
    int Y=findR(y);
    if(X!=Y)printf("No\n");
    else printf("Yes\n");
    }
    int main(){
    cin>>n>>m>>p;
    memset(t,-1,sizeof(t));
    for(i=1;i<=m;i++){
    int x1,x2;
    scanf("%d %d",&x1,&x2);
    mergeR(x1,x2);
    }
    for(i=1;i<=p;i++){
    int x1,x2;
    scanf("%d %d",&x1,&x2);
    findans(x1,x2);
    }
    return 0;
    }

  • 0
    @ 2014-03-21 18:14:58

    #include<iostream>
    #include<cstdio>
    using namespace std;
    int father[50002],a,b,m,n,p;
    int find(int x)
    {

    if (!father[x]) return x;
    father[x]=find(father[x]);

    return father[x];
    }
    int main()
    {

    cin>>n>>m>>p;

    for (int i=1;i<=m;i++)
    {

    cin>>a>>b;

    a=find(a);
    b=find(b);
    father[a]=b;

    }

    for(int i=1;i<=p;i++)
    {

    cin>>a>>b;

    a=find(a);b=find(b);

    if(a==b)printf("Yes");else printf("No");

    }

    return 0;
    }

  • 0
    @ 2014-02-25 22:40:31

    标准并查集,啥也不说了,很简单的程序
    #include <cstdio>
    using namespace std;
    int m,n,p;
    int R[5001]={0};
    int find(int t)
    {
    if(!R[t]) return t;
    else return R[t] = find(R[t]);
    }
    int main()
    {
    scanf("%d %d %d",&n,&m,&p);
    int a,b,x,y;
    for(int i = 0;i < m;i ++)
    {
    scanf("%d %d",&a,&b);
    x = find(a);
    y = find(b);
    if(x != y) R[x] = y;
    }

    for(int i = 0;i < p;i ++)
    {
    scanf("%d %d",&a,&b);
    x = find(a);
    y = find(b);
    printf("%s",(x == y) ? "Yes\n" : "No\n");
    }
    return 0;
    }

  • 0
    @ 2014-01-04 18:47:49
  • 0
    @ 2014-01-01 11:58:47

    Vijos 题解:http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
    有疑问请留言 共同进步

  • 0
    @ 2014-01-01 11:57:32

    Vijos 题解:http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
    有疑问请留言 共同进步

信息

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