P1551 亲戚

作者:hvjg2578
围观群众:310
更新于

题目来源于洛谷


题目链接:https://www.luogu.com.cn/problem/P1551


题目背景

若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。

题目描述

规定:x和y是亲戚,y和z是亲戚,那么x和z也是亲戚。如果x,y是亲戚,那么x的亲戚都是y的亲戚,y的亲戚也都是x的亲戚。

输入格式

第一行:三个整数n,m,p,(n<=5000,m<=5000,p<=5000),分别表示有n个人,m个亲戚关系,询问p对亲戚关系。

以下m行:每行两个数Mi,Mj,1<=Mi,Mj<=N,表示Mi和Mj具有亲戚关系。

接下来p行:每行两个数Pi,Pj,询问Pi和Pj是否具有亲戚关系。

输出格式

P行,每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。

输入输出样例

输入 #1
6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6
输出 #1
Yes
Yes
No

说明/提示

非常简单的并查集入门题哦!!!



我的答案如下

// P1551 亲戚 并查集.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

using namespace std;
int n, m, p;

int fa[50001];

int find(int);
void hebing(int, int);
int main()
{
    cin >> n >> m >> p;
    for (int i = 1; i <= n; i++)
    {
        fa[i] = i;
    }
    for (int count = 1; count <= m; count++)
    {
        int a, b;
        cin >> a >> b;
        hebing(a,b);
    }
    for (int count = 1; count <= p; count++)
    {
        int he1, he2;
        cin >> he1 >> he2;
        int root1, root2;
        root1 = find(he1);
        root2 = find(he2);
        if (root1 == root2)
        {
            cout << "Yes"<<endl;
        }
        else
        {
            cout << "No"<<endl;
        }
    }
    return 0;
}

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

void hebing(int x, int y)
{
    fa[find(x)] = find(y);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件,或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来,若要再次打开此项目,请转到“文件”>“打开”>“项目”并选择 .sln 文件



同时,你还可以对代码进行优化,洛谷上的数据量小,所以上面的代码也能过


代码优化的方法是“路径压缩技术”,即在查找过程中,我们可以把沿途中的每一个节点的根节点都设置为代表节点


find函数可以这么写:

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


完整实现如下

// P1551 亲戚 并查集.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

using namespace std;
int n, m, p;

int fa[50001];

int find(int);
void hebing(int, int);
int main()
{
    cin >> n >> m >> p;
    for (int i = 1; i <= n; i++)
    {
        fa[i] = i;
    }
    for (int count = 1; count <= m; count++)
    {
        int a, b;
        cin >> a >> b;
        hebing(a, b);
    }
    for (int count = 1; count <= p; count++)
    {
        int he1, he2;
        cin >> he1 >> he2;
        int root1, root2;
        root1 = find(he1);
        root2 = find(he2);
        if (root1 == root2)
        {
            cout << "Yes" << endl;
        }
        else
        {
            cout << "No" << endl;
        }
    }
    return 0;
}

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

void hebing(int x, int y)
{
    fa[find(x)] = find(y);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件,或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来,若要再次打开此项目,请转到“文件”>“打开”>“项目”并选择 .sln 文件





    标签: 并查集

    非特殊说明,本文版权归 Chuanrui の 初见之旅 所有,转载请注明出处.

    本文分类: NOIP 2021

    本文标题: P1551 亲戚

    本文网址: https://blog.1314.cool/post/38.html

    • 评论列表

    发表评论:

    ◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

    网站分类
    搜索
    最新留言
    标签列表