/ Vijos / 题库 / 家族 /

题解

282 条题解

  • 0
    @ 2013-12-21 22:16:46

    P1034家族
    Accepted
    记录信息
    评测状态 Accepted
    题目 P1034 家族
    递交时间 2013-12-21 22:13:55
    代码语言 C++
    评测机 VijosEx
    消耗时间 559 ms
    消耗内存 484 KiB
    评测时间 2013-12-21 22:13:57
    评测结果

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 484 KiB, score = 10

    测试数据 #1: Accepted, time = 0 ms, mem = 476 KiB, score = 10

    测试数据 #2: Accepted, time = 15 ms, mem = 484 KiB, score = 10

    测试数据 #3: Accepted, time = 15 ms, mem = 484 KiB, score = 10

    测试数据 #4: Accepted, time = 31 ms, mem = 480 KiB, score = 10

    测试数据 #5: Accepted, time = 31 ms, mem = 480 KiB, score = 10

    测试数据 #6: Accepted, time = 93 ms, mem = 480 KiB, score = 10

    测试数据 #7: Accepted, time = 109 ms, mem = 480 KiB, score = 10

    测试数据 #8: Accepted, time = 125 ms, mem = 480 KiB, score = 10

    测试数据 #9: Accepted, time = 140 ms, mem = 480 KiB, score = 10

    Accepted, time = 559 ms, mem = 484 KiB, score = 100
    代码

    /*
    6 5 3
    1 2
    1 5
    3 4
    5 2
    1 3
    1 4
    2 3
    5 6

    Yes
    Yes
    No
    */
    #include<iostream>
    using namespace std;

    /*合并两个不相交集合
    操作很简单:先设置一个数组Father[x],表示x的“父亲”的编号。
    那么,合并两个不相交集合的方法就是,找到其中一个集合最父亲的父亲(也就是最久远的祖先),将另外一个集合的最久远的祖先的父亲指向它。
    */
    const int MAX = 5000;

    int get_father(int faher[], const int size, int x);
    void Union(int father[], const int size, int x, int y);

    int main(void)
    {
    int father[MAX + 5];
    int n, m, p;
    cin >> n >> m >> p;
    for (int i = 0; i < n + 1; i++)
    {
    father[i] = i;
    }
    int people_a, people_b;
    for (int i = 0; i < m; i++)
    {
    cin >> people_a >> people_b;
    Union(father, MAX + 5, people_a, people_b);
    }
    for (int i = 0; i < p; i++)
    {
    cin >> people_a >> people_b;
    if (get_father(father, MAX + 5, people_a) == get_father(father, MAX + 5, people_b))
    {
    cout << "Yes" << endl;
    }
    else
    {
    cout << "No" << endl;
    }
    }
    return 0;
    }

    void Union(int father[], const int size, int x, int y)
    {
    int fx = get_father(father, size, x);
    int fy = get_father(father, size, y);
    if (fx != fy)
    {
    father[fx] = fy;
    }
    }

    int get_father(int father[], const int size, int x)
    {
    if (father[x] == x)
    return x;
    else
    return get_father(father, size, father[x]);
    }

  • 0
    @ 2013-12-16 13:52:00

    并查集秒过
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int n,m,q;
    int a,b,c,d;
    int f[5005],deep[5005];
    int find(int x)
    {
    if(f[x]!=x)f[x]=find(f[x]);
    return f[x];
    }
    void hebing(int x,int y)
    {
    int i=find(x);
    int j=find(y);
    if(i==j)return ;
    else if(deep[i]>=deep[j])
    {
    deep[i]+=deep[j];
    f[j]=i;

    }
    else
    {
    deep[j]+=deep[i];
    f[i]=j;

    }
    }

    int main()
    {
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
    f[i]=i,deep[i]=1;
    for(int i=1;i<=m;i++)
    {
    cin>>a>>b;
    hebing(a,b);
    }
    for(int i=1;i<=q;i++)
    {
    cin>>c>>d;
    if(find(c)==find(d))
    cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    }

    return 0;
    }

  • 0
    @ 2013-12-15 16:11:33

    第一次写并查集,参考了一下大神的代码
    代码
    #include <iostream>
    #include <string>
    using namespace std;
    #define MAX 5000
    int father[MAX];
    // 初始化
    void Make_set(int x)
    {
    father[x]=x;
    }
    // 查找 father
    int Find_set(int x)
    {
    if(x!=father[x])
    {
    father[x]=Find_set(father[x]);
    }
    return father[x];
    }
    // 合并 x,y在一个集合里
    int Union_set(int x,int y)
    {
    x=Find_set(x);
    y=Find_set(y);
    if(x==y) // 相等说明在同一集合里
    {
    return 0;
    }
    else //不相等 将x的father改为y的father,使x,y在同一集合里
    father[y]=x;
    }
    int main()
    {
    int n,m,p,i,a,b;

    cin>>n>>m>>p;
    // 初始化
    for(i=1;i<=n;i++)
    Make_set(i);
    // 合并 集合
    for(i=1;i<=m;i++)
    {
    cin>>a>>b;
    Union_set(a,b);
    }
    // 查找是否是在同一集合里
    while(p--)
    {
    cin>>a>>b;
    if(Find_set(a)==Find_set(b))
    cout<<"Yes"<<endl;
    else
    cout<<"No"<<endl;
    }
    return 0;
    }

  • 0
    @ 2013-12-02 14:01:21

    并查集模板题……不知为什么n久以前的其他思路都过不了……

    #include <cstdio>
    #include <cstring>
    #include <algorithm>

    int n, m, p;
    #define REP( i, n ) for ( int i = 1; i <= n; i ++ )
    #define FOR( i, a, b ) for ( int i = a; i <= b; i ++ )
    #define DWN( i, a, b ) for ( int i = b; i >= a; i -- )
    #define RST( a, x ) memset ( a, x, sizeof ( a ) );
    #define ONLINE_JUDGE NULL
    #define DISJOINT_SET_USED NULL
    #define NSIZE 6000

    #ifdef DISJOINT_SET_USED

    #ifndef FX
    #define FX father
    #endif
    #ifndef GFX
    #define GFX( x ) GetFather ( x )
    #endif

    int father[ NSIZE ];
    void SetFather ();
    int GetFather ( int x );
    void SetFather ()
    {
    REP ( i, n ) FX[ i ] = i;
    }
    int GetFather ( int x )
    {
    if ( FX[ x ] != x ) FX[ x ] = GetFather ( FX[ x ] );
    return FX[ x ];
    }

    #endif

    using namespace std;
    char out[ 2 ][ 10 ] = { "No", "Yes" };
    int main ()
    {

    #ifndef ONLINE_JUDGE
    freopen ( "P1034.in", "r", stdin );
    freopen ( "P1034.out", "w", stdout );
    #endif

    int t1, t2;
    scanf ( "%d%d%d", &n, &m, &p );
    SetFather ();
    REP ( i, m )
    {
    scanf ( "%d%d", &t1, &t2 );
    if ( GFX ( t1 ) != GFX ( t2 ) ) FX[ FX[ t1 ] ] = FX[ t2 ];
    }
    REP ( i, p )
    {
    scanf ( "%d%d", &t1, &t2 );
    printf ( "%s\n", out[ GFX ( t1 ) == GFX ( t2 ) ] );
    }
    return 0;
    }

  • 0
    @ 2013-10-08 18:34:48

    var f:array[0..5001] of longint; n,m,i,p,a,b,f1,f2:longint;
    Function fa(d:longint):longint;
    var i:longint;
    begin
    if f[d]=d then exit(d);
    f[d]:=fa(f[d]);fa:=f[d];
    end;
    begin
    readln(n,m,p);
    for i:=1 to n do f[i]:=i;
    for i:=1 to m do begin
    readln(a,b); f1:=fa(a);
    f2:=fa(b); f[f1]:=f2; end;
    for i:=1 to p do begin
    readln(a,b); f1:=fa(a); f2:=fa(b);
    if f1=f2 then writeln('Yes') else writeln('No');
    end;
    end.

  • 0
    @ 2013-10-07 13:37:00

    并查集的算法
    var i,j,k,l,n,m,x,y,p:longint;
    father:array[0..10000] of longint;

    function getfather(u:longint):longint;
    begin
    if father[u]=u then exit(u)
    else father[u]:=getfather(father[u]);
    exit(father[u]);
    end;

    procedure union(u,v:longint);
    var fu,fv:longint;
    begin
    fu:=getfather(u);
    fv:=getfather(v);
    if fu<>fv then father[fu]:=fv;
    end;

    begin
    readln(n,m,p);
    for i:=1 to n do father[i]:=i;
    for i:=1 to m do begin
    read(x,y);
    if getfather(x)<>getfather(y) then union(x,y);
    end;
    for i:=1 to p do begin
    read(x,y);
    if getfather(x)<>getfather(y) then writeln('No')
    else writeln('Yes');
    end;
    end.

  • 0
    @ 2013-10-01 09:33:35

    var
    f:array[1..5000]of integer;
    m,n,p,x,y,x1,y1:integer;
    j:longint;

    function find(i:integer):integer;
    begin
    if f[i]=i then exit(i);
    f[i]:=find(f[i]);
    exit(f[i]);
    end;

    BEGIN
    readln(n,m,p);
    for j:=1 to n do f[j]:=j;
    for j:=1 to m do
    begin
    readln(x,y);
    x1:=find(x);
    y1:=find(y);
    if x1<>y1 then f[x1]:=y1;
    end;
    for j:= 1 to p do
    begin
    readln(x,y);
    x1:=find(x);
    y1:=find(y);
    if x1=y1 then writeln('Yes')
    else writeln('No');
    end;
    end.

    //代码有点长,可以简化

  • 0
    @ 2013-05-12 01:22:48

    坑死爹了
    调了两个小时的wrong answer
    原来还要加**"\n"**

  • 0
    @ 2012-11-07 08:23:42

    编译通过...

    ├ 测试数据 01:答案正确... (0ms, 692KB)

    ├ 测试数据 02:答案正确... (0ms, 692KB)

    ├ 测试数据 03:答案正确... (0ms, 692KB)

    ├ 测试数据 04:答案正确... (0ms, 692KB)

    ├ 测试数据 05:答案正确... (0ms, 692KB)

    ├ 测试数据 06:答案正确... (0ms, 692KB)

    ├ 测试数据 07:答案正确... (0ms, 692KB)

    ├ 测试数据 08:答案正确... (0ms, 692KB)

    ├ 测试数据 09:答案正确... (0ms, 692KB)

    ├ 测试数据 10:答案正确... (0ms, 692KB)

    ---|---|---|---|---|---|---|---|-

    Accepted / 100 / 3ms / 692KB

  • 0
    @ 2012-10-09 20:53:58

    var

    n,m,p,a,mi,mj,d:integer;

    e:array[1..5000]of integer;

    h:array[1..5000,1..5000]of integer;

    begin

    read(n,m,p);

    for a:=1 to m do begin

    read(mi,mj); if (mi>=1)and(mj

  • 0
    @ 2012-08-24 08:30:25

    算法:并查集

  • 0
    @ 2012-08-04 08:07:52

    点击查看代码

  • 0
    @ 2012-07-29 19:31:26

    规模较弱,Floodfill/并查集均可..首先Floodfill的咱果然是个奇葩么0.0

  • 0
    @ 2012-07-29 14:51:29

    并查集

    注意合并a,b的时候一定要让a的树根指向b的树根,否则会WA

    样例数据即使在你写错(上面那个地方)的情况下答案也是一样的

  • 0
    @ 2012-07-12 15:40:09

    #include

    const int maxn=5005;

    int p[maxn];

    int find(int x)

    {

    return x==p[x]?x:p[x]=find(p[x]);

    }

    void Union(int x,int y)

    {

    x=find(x); y=find(y);

    p[x]=y;

    }

    int main()

    {

    int n,m,q,i,x,y;

    scanf("%d%d%d",&n,&m,&q);

    for(i=1;i

  • 0
    @ 2010-07-04 09:54:10

    var

    a,b:array[1..5000]of integer;

    i,j,k,n,m,x,y,p:integer;

    function find(x:integer):integer;

    begin

    if xa[x] then a[x]:=find(a[x]);

    find:=a[x];

    end;

    begin

    readln(n,m,p);

    for i:=1 to n do

    begin

    a[i]:=i; b[i]:=1;

    end;

    for i:=1 to m do

    begin

    readln(x,y);

    x:=find(x); y:=find(y);

    if xy then

    if b[x]=b[y] then

    begin

    b[x]:=b[x]+1; a[y]:=x;

    end

    else if b[x]>b[y] then a[y]:=x

    else a[x]:=y;

    end;

    for i:=1 to p do

    begin

    readln(x,y);

    if find(x)=find(y) then writeln('Yes')

    else writeln('No');

    end;

    end.

  • 0
    @ 2010-07-03 18:08:29

    var

    i1,i2,i,m,n,p,p1,q:longint;

    father:array[1..5000]of integer;

    function find(kk:longint):longint;

    var j:longint;

    begin

    j:=kk;

    while father[j]0 do j:=father[j];

    find:=j;

    end;

    begin

    read(n,m,p);

    fillchar(father,sizeof(father),0);

    for i:=1 to m do

    begin

    read(i1,i2);

    p1:=find(i1);

    q:=find(i2);

    if p1q then father[q]:=p1;

    end;

    for i:=1 to p do

    begin

    read(i1,i2);

    p1:=find(i1);

    q:=find(i2);

    if (p1=0)or(q=0)or(p1=q) then writeln('Yes')

    else writeln('No');

    end;

    end.

  • 0
    @ 2010-04-14 21:38:04

    Program relative;

    var

    x,y,n,m,p,i,a,b:longint;

    father:array[1..5000] of longint;

    function find(i:longint):longint;

    begin

    if father[i]=0 then exit(i);

    father[i]:=find(father[i]);

    exit(father[i]);

    end;{find}

    Begin

    fillchar(father,sizeof(father),0);

    readln(n,m,p);//读入初始数据;

    for i:=1 to m do//{处理亲缘关系}

    begin

    readln(a,b);

    x:=find(a);

    y:=find(b);

    if xy then father[x]:=y;//判断a,b根节点是否相同,不同则加入亲戚系统;

    end;{for}

    for i:=1 to p do

    begin

    readln(a,b);

    if find(a)=find(b) then writeln('Yes') else writeln('No');//询问a,b是否是亲戚;

    end;{for}

    End.{main}

  • 0
    @ 2010-04-14 11:52:50

    #include

    int f[5001],m,n,p;

    int q[5001];

    void init()

    {

    int i;

    for(i=1;i

信息

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