P3026 题解-mnesia

mnesia · 2021-07-15 16:44:13 · 题解

这道题是一道典型的并查集算法题。

刚看到这道题时，第一感觉是需要可能需要对并查集做一些优化，或者说把并查集分为两个部分，一部分存储牛的数据，另一部分存储语言的数据。后来的实现过程大体跟思路相同，但是意识到了前半部分数组（编号 1 ~ N）可以用来存储牛，后半部分数组（编号 N + 1 ~ N + M）可以用来存储语言 这一技巧。另外就是如其他题解所说，在标记牛与语言的关系时，只需要把第一头会这种语言的牛的编号作为一个“代表”赋值给对应的语言所在的数组空间，接下来的牛只需要连向对应的语言即可。

思路仅凭语言很难解释清楚，下面给出代码：

#include<iostream>
#include<stdio.h>

using namespace std;
const int maxn = 10010;
const int maxm = 30010;
int n, m;
int num;
int k;
int father[maxn];
int lang[maxm];//lang[i] 存储会第 i 种语言的牛的编号（只存一头） 
int cnt;//cnt 存储当前需要买的书本数，初始化为 n（开始时视为所有牛都不会任一语言） 

void init()
{
    cnt = n;
    for(int i = 1;i <= n;i++)
    {
        father[i] = i;
    }
    return ;
}

int Find(int x)
{
    if(x != father[x])
    {
        father[x] = Find(father[x]);
    }
    return father[x];
}

void Union(int x, int y)
{
    int a = Find(x);
    int b = Find(y);
    if(a != b)
    {
        father[a] = b;
        cnt--;
    }
    return ;
}

int main()
{
//  freopen("learning.in", "r", stdin);
//  freopen("learning.out", "w", stdout);
    cin >> n >> m;
    init();
    for(int i = 1;i <= n;i++)
    {
        cin >> k;
        for(int j = 1;j <= k;j++)
        {
            cin >> num;
            if(lang[num] != 0)//如果之前已经有牛会第 i 种语言了 
            {
                Union(i, lang[num]);//将第 i 头牛加入到会第 num 种语言的集团中 
            }
            else
            {
                lang[num] = i;//将第 i 头牛设置为会第 num 种语言的代表 
            }
        }
    }
    cout << cnt - 1;
    return 0;
}

这里注意最后输出时要输出 cnt - 1 ，因为如果有 cnt 种语言需要购买书籍以达到所有牛都能相互交流的目的，只需要有 cnt - 1 种语言被对应的牛精通，剩下的一种语言对应的牛就一定能通过与其他牛的交流来间接达成与特定的牛交流的目的。