ACM 题目：亲戚

20 August 2014

题目

Problem Description

或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。如果能得到完整的家谱，判断两个人是否是亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱非常庞大，那么验证亲戚关系是非人力所能及。在这种情况下，最好的帮手是计算机。为了将问题简化，你将得到一些亲戚关系的信息，如Marry和Tom是亲戚，Tom和Ben是亲戚等。从这些信息中，你可以推出Marry和Ben是亲戚。请写一个程序，对于我们关于亲戚关系的提问，以最快的速度给出答案。

Input

输入有多组数据，每组数据由两个部分组成，第一部分以N,M开始，N为问题涉及的人数(1<=N<=10000)。这些人的编号为1,2,3,...,N。下面有M行(1<=M<=1000000)，每行两个数ai，bi表示已知ai和bi是亲戚。
第二部分以Q开始。以下Q行有Q个询问(1<=Q<=100000)，每行为ci，di表示询问ci和di是否为亲戚。

Output

对于每组输入数据，对于每个询问ci，di，输出一一行，若ci和di为亲戚，则输出“Yes”，否则输出“No”。

Sample Input

10 7
2 4
5 7
1 3
8 9
1 2
5 6
2 3
3
3 4
7 10
8 9

Sample Output

Yes
No
Yes

解题思路

并查集的简单应用

解题代码

//
//  main.cpp
//  亲戚
//
//  Created by Yeah on 14-8-18.
//  Copyright (c) 2014年 Yeah. All rights reserved.
//

#include <iostream>
using namespace std;

#define MAX_N 100001

int Par [MAX_N];
int Rank[MAX_N];

void init(int n)
{
    for (int i(1); i <= n; i++)
    {
        Par [i] = i;
        Rank[i] = 0;
    }
}

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

void unite(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y)
    {
        return;
    }
    
    if (Rank[x] < Rank[y])
    {
        Par[x] = y;
    }
    else
    {
        Par[y] = x;
        if (Rank[x] == Rank[y])
        {
            Rank[x]++;
        }
    }
}

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

int main()
{
    int N(0), M(0);
    while (scanf("%d%d", &N, &M) != EOF)
    {
        init(N);
        int ai(0), bi(0);
        while (M--)
        {
            scanf("%d%d", &ai, &bi);
            unite(ai, bi);
        }
        int Q(0);
        scanf("%d", &Q);
        int ci(0), di(0);
        while (Q--)
        {
            scanf("%d%d", &ci, &di);
            printf(same(ci, di) ? "Yes\n" : "No\n");
        }
    }
    return 0;
}
题目链接：暂无
blog comments powered by Disqus