/ Vijos / 题库 / 家族 /

题解

283 条题解

  • 0
    @ 2016-08-06 19:38:40 
    #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long lg;
#define min(a,b) (a>b?b:a)
#define max(a,b) (a>b?a:b)
#define MAXX 200011
//#define OPEN 

lg n,m,k,s,a,b,f[MAXX];

lg read()
{
    lg res=0;
    char c;
    while((c=getchar())>='0' && c<='9')
      res=res*10+c-'0';
    return res;
}

void out(lg n)
{
    if(n>9) out(n/10);
    putchar(n%10+'0');
}

lg find(int n)
{
    return f[n]==n ? n:(f[n]=find(f[n]));
}

int main(int argc, char** argv)
{
#ifdef OPEN
   freopen("data.in","r",stdin);
#endif
    n=read();
    m=read();
    s=read();
    for(int i=1;i<=n;i++)
        f[i]=i;
    for(int i=1;i<=m;i++)
    {
        a=find(read());
        b=find(read());
        if(a!=b)
            f[a]=b;
    }
    for(int i=1;i<=s;i++)
    {
        a=find(read());
        b=find(read());
        if(a!=b)
            puts("No");
        else
            puts("Yes");
    }
    return 0;
}
  • 0
    @ 2016-07-18 13:28:17

    并查集。
    ~~~
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>

    using namespace std;
    const int N=10005;
    const int INF=0x3f3f3f3f;

    struct UFS{
    int set[N];
    int operator {
    return set[x];
    }
    void MAKE_SET(int x){
    set[x]=x;
    }
    int FIND_SET(int x){
    if(x!=set[x]) set[x]=FIND_SET(set[x]);
    return set[x];
    }
    void UNION(int x,int y){
    x=FIND_SET(x);
    y=FIND_SET(y);
    if(x!=y) set[x]=y;
    }
    };

    UFS T;
    int n,m,p,u,v;
    int main(){
    scanf("%d%d%d",&n,&m,&p);
    for(int i=1;i<=n;i++)
    T.MAKE_SET(i);
    for(int i=1;i<=m;i++){
    scanf("%d%d",&u,&v);
    T.UNION(u,v);
    }
    for(int i=1;i<=p;i++){
    scanf("%d%d",&u,&v);
    if(T.FIND_SET(u)==T.FIND_SET(v))
    printf("Yes\n");
    else printf("No\n");
    }
    return 0;
    }

  • 0
    @ 2016-07-15 19:47:11

    #include<cstdio>
    #include<iostream>
    using namespace std;
    int bin[1002];
    int findx(int x)
    {
    int r=x;
    while(bin[r] !=r)
    r=bin[r];
    return r;
    }
    void merge(int x,int y)
    {
    int fx,fy;
    fx = findx(x);
    fy = findx(y);
    if(fx != fy)
    bin[fx] = fy;
    }
    int main(){
    freopen("bin.in","r",stdin);
    freopen("bin.out","w",stdout);
    int x,y,i,m,n,p;
    cin>>n>>m>>p;
    {
    for(i=1;i<=n;i++)
    bin[i] = i;
    for(i=1;i<=m;i++)
    {
    scanf("%d %d",&x,&y);
    merge(x,y);
    }
    for(i=1;i<=p;i++){
    cin>>x>>y;
    if(findx(x)==findx(y))
    cout<<"Yes"<<endl;
    else
    cout<<"No"<<endl;
    }
    }

    }

  • 0
    @ 2016-07-10 11:01:32

    裸并查集

    #include <iostream>

using namespace std;

const int maxn = 5000 + 5;

int data[maxn];
int tree[maxn];
int height[maxn];

void Build(int n)
{
    for (int i = 0; i < n; i++)
    {
        tree[i] = i;
        height[i] = 0;
    }
}

int Find(int n)
{
    if (n == tree[n])
        return n;
    return tree[n] = Find(tree[n]);
}

void Unite(int a, int b)
{
    a = Find(a);
    b = Find(b);
    if (a == b)
        return ;
    if (height[a] < height[b])
        tree[a] = b;
    else
    {
        tree[b] = a;
        if (height[a] == height[b])
            height[a]++;
    }
}

string Query(int a, int b)
{
    if (Find(a) == Find(b))
        return "Yes";
    else
        return "No";
}

int main()
{
    int n, m, p;
    while(cin >> n >> m >> p)
    {
        Build(n);
        for (int i = 0; i < m; i++)
        {
            int a, b;
            cin >> a >> b;
            Unite(a, b);
        }
        for (int i = 0; i < p; i++)
        {
            int a, b;
            cin >> a >> b;
            cout << Query(a, b) << endl;
        }
    }
    
    return 0;
}
  • 0
    @ 2016-06-13 23:38:18

    瞎写的递归主函数……其实能用的，还能A
    ```C++
    #define _CRT_SECURE_NO_DEPRECATE
    #include <stdio.h>
    #include<iostream>
    #include<set>
    #include<stdlib.h>
    #include<string>
    #include<cstring>
    using namespace std;

    long father[50000] = { 0 };
    long found(long node)
    {
    if (father[node] == node) return node;
    father[node] = found(father[node]);
    return father[node];
    }

    void bringcharge(long l, long r)
    {
    l = found(l);
    r = found(r);
    if (l != r) father[r] = l;
    return;
    }
    long a[] = { 1, 2, 3, 0 };
    long n, m, q;
    long *qqq = a;

    int main(long *rr)
    {
    rr = qqq++;
    if (*rr == 1){
    ios::sync_with_stdio(false);
    cin >> n >> m >> q;
    for (long i = 1; i <= n; i++)
    father[i] = i;
    main(qqq);
    }
    else if (*rr == 2){
    for (long i = 1; i <= m; i++)
    {
    long l, r;
    cin >> l >> r;
    bringcharge(l, r);
    }
    main(qqq);
    }
    else if (*rr == 3)
    {
    for (long i = 1; i <= q; i++)
    {
    long l, r;
    cin >> l >> r;
    if (found(l) != found(r))cout << "No" << endl;
    else cout << "Yes" << endl;
    }
    main(qqq);
    }
    // system("pause");
    else exit(0);
    }
    ```

  • 0
    @ 2016-06-13 21:46:13 
    #include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
int arr[5010];
int find(int a)//查找a的根节点，并返回
{
    if (arr[a] == a) return a;
    else arr[a] = find(arr[a]);
    return arr[a];
}
void initial(int m)
{
    int a, b, t1, t2;
    for (int i = 0; i<m; i++)
    {
        cin >> a >> b;
        t1 = find(a);
        t2 = find(b);
        if (t1 != t2) { arr[b] = t1; arr[t2] = t1; }//用find函数来找a和b的根节点，看他们是否相等，相等就不管，不等就让b的根节点指向a的根节点
    }
}
void check(int p)
{
    int a, b;
    for (int i = 0; i<p; i++)
    {
        cin >> a >> b;
        a = find(a);
        b = find(b);
        if (a==b) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}
int main()
{
    for (int i = 0; i<5008; i++)//初始化，让arr[i]上的值指向自己
        arr[i] = i;
    int n, m, p;
    cin >> n >> m >> p;
    initial(m);
    check(p);
    //system("pause");
    return 0;
}
  • 0
    @ 2016-05-12 13:51:19

    //并查集水水的过了
    #include<cstdio>
    int father[5000];

    int find_father(int v)
    {
    if(father[v]==v)
    return v;
    father[v]=find_father(father[v]);
    return father[v];
    }

    void merge(int p,int q)
    {
    int i,j;
    i=find_father(p);
    j=find_father(q);
    father[i]=j;
    }

    bool judge(int x,int y)
    {
    int i=find_father(x),j=find_father(y);
    if(i==j)
    return true;
    else
    return false;
    }

    int main()
    {
    int n,m,p,i,j;
    scanf("%d%d%d",&n,&m,&p);
    for(i=1;i<=n;i++)
    {
    father[i]=i;
    }
    for(i=1;i<=m;i++)
    {
    int x,y;
    scanf("%d%d",&x,&y);
    merge(x,y);
    }
    for(i=1;i<=p;i++)
    {
    int x,y;
    scanf("%d%d",&x,&y);
    if(judge(x,y))
    puts("Yes");
    else
    puts("No");
    }
    }

  • 0
    @ 2016-03-20 10:46:34

    测试数据 #0: Accepted, time = 0 ms, mem = 572 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 572 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 568 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 572 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 568 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 568 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 572 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 572 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 568 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 572 KiB, score = 10
    Accepted, time = 0 ms, mem = 572 KiB, score = 100
    代码
    #include<cstdio>
    #include<iostream>
    using namespace std;

    const int Max = 5000 + 10;

    int N, M ,P, A, B, Parent[Max];

    inline int getInt() {
    int Return = 0;
    char Get = getchar();
    while(Get >= '0' && Get <= '9') {
    Return = Return * 10 + (Get - '0');
    Get = getchar();
    }
    return Return;
    }

    inline int Find(int theElement) {
    int theRoot = theElement;
    while (Parent[theRoot] != theRoot)
    theRoot = Parent[theRoot];
    int parentNode;
    int Now = theElement;
    while(Now != theRoot) {
    parentNode = Parent[Now];
    Parent[Now] = theRoot;
    Now = Parent[Now];
    }
    return theRoot;
    }

    int main() {
    N = getInt(); M = getInt(); P = getInt();
    for(int i = 1; i <= N; ++i) Parent[i] = i;
    for(int i = 1; i <= M; ++i) {
    A = getInt(); B = getInt();
    A = Find(A); B = Find(B);
    if(A != B) Parent[B] = A;
    }
    for(int i = 1; i <= P; ++i) {
    A = getInt(); B = getInt();
    if(Find(A) == Find(B)) printf("Yes\n");
    else printf("No\n");
    }
    return 0;
    }

  • 0
    @ 2016-02-19 11:28:08

    垃圾版题解：
    c++
    #include<stdio.h>
    #include<string.h>
    int f[5001]={0};
    int ff(int a){
    if(f[a]==0) return a;else
    return f[a]=ff(f[a]);
    }
    int main(){
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int a,b,i=0;i<m;++i){
    scanf("%d%d",&a,&b);
    int x=ff(a),y=ff(b);
    if(x!=y) f[x]=y;
    }
    for(int a,b,i=0;i<k;++i){
    scanf("%d%d",&a,&b);
    printf("%s\n",ff(a)==ff(b)?"Yes":"No");
    }
    }

  • 0
    @ 2016-02-02 10:24:41

    555，原来输出没换行WA了
    #include<iostream>
    using namespace std;
    int pa[5001];
    int findset(int x)
    {
    return pa[x]!=x?pa[x]=findset(pa[x]):x;
    }
    int main()
    {
    int n,m,p;
    cin>>n>>m>>p;
    for (int i=1;i<=n;i++)
    pa[i]=i;
    int a,b,x,y;
    for (int i=1;i<=m;i++)
    {
    cin>>a>>b;
    x=findset(a);y=findset(b);
    if (x!=y)pa[x]=y;
    }

    for (int i=1;i<=p;i++)
    {
    cin>>a>>b;
    x=findset(a);y=findset(b);
    if (x==y)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    }
    }

  • 0
    @ 2015-11-03 10:32:35

    program p1034;
    var
    father:array[1..6000] of longint;
    n,m,p,i,x,y:longint;
    function getfather(x:longint):longint;
    begin
    if father[x]=x then
    exit(x)
    else begin
    father[x]:=getfather(father[x]);
    exit(father[x]);
    end;
    end;
    procedure merge(x,y:longint);
    var
    fa1,fa2:longint;
    begin
    fa1:=getfather(x);
    fa2:=getfather(y);
    father[fa1]:=fa2;
    end;
    function judge(x,y:longint):boolean;
    var
    fa1,fa2:longint;
    begin
    fa1:=getfather(x);
    fa2:=getfather(y);
    if fa1=fa2 then
    judge:=true
    else judge:=false;
    end;
    {main}
    begin
    readln(n,m,p);
    for i:=1 to n do
    father[i]:=i;
    for i:=1 to m do
    begin
    readln(x,y);
    merge(x,y);
    end;
    for i:=1 to p do
    begin
    readln(x,y);
    if judge(x,y) then
    writeln('Yes')
    else writeln('No');
    end;
    end.

  • 0
    @ 2015-10-29 13:05:15

    #include <cstdio>

    using namespace std;

    int n=0,m=0,p=0,set[5001];

    int root(int n) {
    int path[5001],len=0;
    while (set[n]!=n) {
    path[len++]=n;
    n=set[n];
    }
    for (int i=0;i<len;++i)
    set[path[i]]=n;
    return n;
    }

    int main(void) {
    scanf("%d %d %d",&n,&m,&p);
    for (int i=1;i<=n;++i)
    set[i]=i;
    for (int i=0;i<m;++i) {
    int a=0,b=0;
    scanf("%d %d",&a,&b);
    set[b]=a;
    }
    for (int i=0;i<p;++i) {
    int a=0,b=0;
    scanf("%d %d",&a,&b);
    if (root(a)==root(b))
    printf("Yes\n");
    else
    printf("No\n");
    }
    return 0;
    }

    QwQ 我好菜

  • 0
    @ 2015-10-26 20:00:15

    我什么也不知道
    var
    f:array[0..5009] of longint;
    x,y,fx,fy,i,n,m,p:longint;
    function find(x:longint):longint;
    begin
    if f[x]=x then exit(x);
    f[x]:=find(f[x]); exit(f[x]);
    end;
    begin
    readln(n,m,p);
    for i:=1 to n do f[i]:=i;
    for i:=1 to m do
    begin
    read(x,y);
    fx:=find(x);
    fy:=find(y);
    if fx<>fy then f[fx]:=fy;
    end;
    for i:=1 to p do
    begin
    read(x,y);
    if find(x)=find(y)
    then writeln('Yes') else writeln('No');
    end;
    end.

  • 0
    @ 2015-10-01 11:47:27

    注意两根相同的判断
    。。。。
    #include <stdio.h>
    #include <iostream>
    using namespace std;
    int rt[10010]={0},n,m,q;

    int find(int p){
    if(rt[p]==0)
    return p;
    else{
    rt[p]=find(rt[p]);
    return rt[p];
    }
    }

    int main(){
    int i,j,k,x,y;
    scanf("%d%d%d",&n,&m,&q);
    for(i=1;i<=m;++i){
    scanf("%d%d",&x,&y);
    j=find(x);
    k=find(y);
    if(j!=k){
    rt[j]=k;
    }
    }
    for(i=1;i<=q;++i){
    scanf("%d%d",&x,&y);
    if(find(x)==find(y)) printf("Yes\n");
    else printf("No\n");
    }
    }

  • 0
    @ 2015-08-27 17:39:38

    http://www.cnblogs.com/oierforever/p/4763790.html

  • 0
    @ 2015-08-25 09:30:45

    AC 35道纪念
    弱弱的 并查集AC
    编译成功

    测试数据 #0: Accepted, time = 14 ms, mem = 556 KiB, score = 10
    测试数据 #1: Accepted, time = 15 ms, mem = 564 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 560 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 560 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 564 KiB, score = 10
    测试数据 #5: Accepted, time = 31 ms, mem = 556 KiB, score = 10
    测试数据 #6: Accepted, time = 94 ms, mem = 560 KiB, score = 10
    测试数据 #7: Accepted, time = 78 ms, mem = 560 KiB, score = 10
    测试数据 #8: Accepted, time = 109 ms, mem = 556 KiB, score = 10
    测试数据 #9: Accepted, time = 109 ms, mem = 560 KiB, score = 10
    Accepted, time = 465 ms, mem = 564 KiB, score = 100
    代码
    include <iostream>
    include <cstdio>
    include <algorithm>
    using namespace std;
    int i,j,n,m,z,k,l,q,p,s1,s2;
    int a[10002];
    char f[10002];
    int find(int x)
    {
    if (a[x]==0) return x;
    else if (a[a[x]]==0) return a[x];
    a[x]=find(a[x]);
    return a[x];
    }
    int main()
    {
    l=1;
    cin>>n>>m>>z;
    for (i=1;i<=m;i++)
    {
    cin>>s1>>s2;
    q=find(s1); p=find(s2);
    if (q!=p) a[q]=p;
    }
    for (i=1;i<=z;i++)
    {
    cin>>s1>>s2;
    q=find(s1); p=find(s2);
    if (q==p) {f[l]='y'; l++;}
    else {f[l]='n';l++;}
    }
    for (i=1;i<=l-1;i++)
    if (f[i]=='y') cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    }

  • 0
    @ 2015-08-23 11:33:06

    裸的并查集
    #include <cstdio>
    #define maxn 5005
    int rep[maxn];
    int findRep(int x)
    {
    return rep[x]==x?x:rep[x]=findRep(rep[x]);
    }

    int main()
    {
    int n,m,p;scanf("%d%d%d",&n,&m,&p);
    for(int i=1;i<=n;i++) rep[i]=i;
    for(int i=1;i<=m;i++) {
    int x,y;scanf("%d%d",&x,&y);
    int r1=findRep(x),r2=findRep(y);
    rep[r2]=r1;

    }
    for(int i=1;i<=p;i++) {
    int x,y;scanf("%d%d",&x,&y);
    //if(rep[x]==rep[y]) printf("Yes\n");
    int r1=findRep(x),r2=findRep(y);
    if(r1==r2) printf("Yes\n");
    else printf("No\n");
    }
    return 0;
    }

  • 0
    @ 2015-08-14 20:28:51

    记录信息
    评测状态 Accepted
    题目 P1034 家族
    递交时间 2015-07-11 11:55:58
    代码语言 C++
    评测机 VijosEx
    消耗时间 60 ms
    消耗内存 4192 KiB
    评测时间 2015-07-11 11:56:04
    评测结果
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 4192 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 4192 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 4192 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 4188 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 4188 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 4192 KiB, score = 10
    测试数据 #6: Accepted, time = 15 ms, mem = 4188 KiB, score = 10
    测试数据 #7: Accepted, time = 15 ms, mem = 4192 KiB, score = 10
    测试数据 #8: Accepted, time = 15 ms, mem = 4192 KiB, score = 10
    测试数据 #9: Accepted, time = 15 ms, mem = 4188 KiB, score = 10
    Accepted, time = 60 ms, mem = 4192 KiB, score = 100
    代码
    #include <iostream>
    #include <string.h>
    #include <stdio.h>
    using namespace std;
    int relative[1000000];
    int find(int a)
    {
    if(relative[a]==a)
    return a;
    else return relative[a]=find(relative[a]);
    }
    int main()
    {
    int n,k,q;
    scanf("%d%d%d",&n,&k,&q);
    for(int i=1;i<=n;i++)
    relative[i]=i;

    for(int i=1;i<=k;i++)
    {
    int x,y;
    scanf("%d%d",&x,&y);
    int rex=find(x);
    int rey=find(y);
    relative[rex]=rey;
    }

    for(int i=1;i<=q;i++)
    {
    int x,y;
    scanf("%d%d",&x,&y);
    if(find(x)==find(y))
    printf("Yes\n");
    else
    printf("No\n");

    }
    }

  • 0
    @ 2015-08-07 17:08:52

    var
    a:array[1..5000]of longint;
    p,n,m,i,x,y,f1,f2:longint;
    function fa(s:longint):longint;
    var t,tt:longint;
    begin
    t:=s;
    while t<>a[t] do
    t:=a[t];
    while s<>a[s] do
    begin
    tt:=s;
    s:=a[s];
    a[tt]:=t;
    end;
    end;
    begin
    read(n,m,p);
    for i:=1 to n do
    a[i]:=i;
    for i:=1 to m do
    begin
    read(x,y);
    a[y]:=x;
    end;
    for i:=1 to p do
    begin
    read(x,y);
    f1:=fa(x);
    f2:=fa(y);
    if f1=f2 then writeln('Yes')
    else writeln('No');
    end;
    end.

  • 0
    @ 2015-06-14 17:45:45

    #include<cstdio>
    using namespace std;

    int pre[5050];

    int Find(int x)
    {
    int r=x;
    while(r!=pre[r])
    r=pre[r];

    int i=x,j;
    while(pre[i]!=r)
    {
    j=pre[i];
    pre[i]=r;
    i=j;
    }
    return r;
    }

    void mix(int x,int y)
    {
    int fx=Find(x),fy=Find(y);
    if(fx!=fy)
    {
    pre[fy]=fx;
    }
    }

    int main()
    {
    int n,m,p,i,a,b;
    scanf("%d%d%d",&n,&m,&p);

    for(i=1;i<=n;i++)
    pre[i]=i;
    for (i=1;i<=m;i++)
    {
    scanf("%d%d",&a,&b);
    if (Find(a)!=Find(b))
    mix(a,b);
    }

    for (i=1;i<=p;i++)
    {
    scanf("%d%d",&a,&b);
    if (Find(a)==Find(b))
    printf("Yes\n");
    else
    printf("No\n");
    }
    return 0;
    }

家族

信息

ID
1034
难度
4
分类
数据结构 | 并查集 点击显示
标签
(无)
递交数
9379
已通过
3848
通过率
41%
被复制
16
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1