Rumor 并查集模板题

Rumor

Vova 对自己发誓，绝不再玩电脑游戏…… 但最近，知名的游戏开发商暴火娱乐有限公司，发布了他们的最新游戏 “World of Farcraft”，并且该游戏变得非常流行。显然，Vova 又开始玩这款游戏。

现在，他尝试解决一个任务。这项任务是，来到一个名叫 Overcity 的定居点，并在里面散播谣言。

Vova 知道，在 Overcity 有 n 个人物角色。某些人物角色互为朋友，他们共享所获得的信息。Vova 也知道，他可以给每个人物角色好处，以便人物角色开始散播谣言；第 i 个人物角色想要 ci 的黄金，作为散播谣言的交换。当一个人物角色听到了谣言之后，他就告诉自己的所有朋友，他的朋友们也开始散播谣言给自己的朋友 (免费)，依此类推。

当全部的 n 个人物角色都听到了谣言时，任务完成。请问，Vova 至少需要多少黄金，才能完成这项任务？

如果你对题意仍有疑问，请参见样例说明。

输入格式
第一行包含两个整数 n 和 m (1 ≤ n ≤ 105, 0 ≤ m ≤ 105)，分别表示 Overcity 的人物角色数量，以及存在多少对的朋友关系。

第二行包含 n 个整数 ci (0 ≤ ci ≤ 109) 表示第 i 个人物角色需要的黄金，以便开始散播谣言。

接下来的m 行，每行包含两个数 (xi, yi)，表示人物角色 xi 和 yi 是朋友关系 (1 ≤ xi, yi ≤ n, xi ≠ yi)。数据保证，每对朋友最多被列出一次。

输出格式
打印一个数，表示 Vova 为了完成任务所必须花费的最少黄金。

输入输出样例
输入
5 2
2 5 3 4 8
1 4
4 5
输出
10
输入
10 0
1 2 3 4 5 6 7 8 9 10
输出
55
输入
10 5
1 6 2 7 3 8 4 9 5 10
1 2
3 4
5 6
7 8
9 10
输出
15
样例说明
在第一个样例中，最优决策是给第 1 个人物角色好处 (他将会散播谣言给第 4 个人物角色，并且第 4 个人物角色会散播谣言给第 5 个人物角色)。同时，Vova 还必须给第 2 个、第 3 个人物角色，分别给予好处，以便他们得知谣言。

在第二个样例中，Vova 必须给每个人好处。

在第三个样例中，最优决策是给第 1 个、第 3 个、第 5 个、第 7 个、第 9 个人物角色，分别予以好处。

思路 ：
这道题其实没有什么好说的 是一道并查集的板子题 我们需要去对输入的数据进行路径压缩 然后在后面进行pre[i]==i 的判断就好了
PS：这道题是有坑点的 就是我们的find函数不可以写成while循环的形式 应该写成递归的形式 用空间去换时间 否则会Time Limit

AC代码：

//并查集
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
int book[100000+10];
int pre[100000+10];
int find(int i)
{
    return pre[i]==i?i:(pre[i]=find(pre[i]));
}
int m,n;
int tmpa,tmpb;
int main()
{
    cin >> m >> n;
    for(int i=1;i<=m;i++)
    cin >> book[i];
    for(int i=1;i<=m;i++)
    pre[i]=i;
    for(int i=0;i<n;i++)
    {
        cin >> tmpa >> tmpb;
        int flaga=find(tmpa);
        int flagb=find(tmpb);
        pre[flaga]=flagb;     //路径压缩
    }
    for(int i=1;i<=m;i++)
    book[find(i)]=min(book[find(i)],book[i]);
    ll sum=0;
    for(int i=1;i<=m;i++)
    {
        if(pre[i]==i)
        sum+=book[i];
    }
    cout << sum << endl;
    return 0;
}