在广大的算法世界中，有一种神奇的算法（数据结构）叫做并查集，这个中文可能还是不很好理解，但看看它的英文大概就知道是什么了: Disjoint-set Data Structure。
顾名思义，这样的数据结构主要用来解决的是不相交的系列间的集合之间关系，如查找，合并等。
要实现并查集，我们需要实现三个功能
1、并：将相交的两个集合合并为一个集合
2、查：查找指定的元素在哪个集合中
3、集：将每个元素创建为集合
（至少我是这样理解的（逃
这样的话，对于所有元素，我们可以将他们分到各自所属的集合。
举个例子，A 与 B 是亲戚，B 与C 是亲戚，D 与 F 是亲戚，那么通过并查集操作，我们就可以将该例中的两个家族找出（ABC） 与 （DF）。
具体实现
这个实现应该是按照集查并的顺序实现的。
我们规定，所有的集合中，有且只有一个元素为这个集合的代表，这样集合就可以用树状结构来储存，所有元素的父亲都指向能代表他的元素（也就是说明这两个元素在同一集合），一个集合中的所有元素最终指向唯一元素，即该集合代表。那么我们可以用一个数组来储存每个元素的父亲，建立集合的操作即是将集合中的各个位置赋值为自己的下标，因为这时每个集合都只有一个元素。接着，查找的操作即为递归查找数组中值等于下标的元素所在的位置。合并两个集合只需将一个集合的代表指向另一个集合的代表，让另一个集合的代表来代表这两个集合就可以了
接着是一道题目：http://codeforces.com/problemset/problem/893/C
题目太长就只贴链接了
我最开始想的是用结构体将一个元素（人）的父亲和他的消费合在一起并存在数组中，但这样操作的话在后面的找集合中最小消费就比较麻烦，因为还要遍历整个树结构，后面干脆先另外开一个集合来存每个人的消费，后面再遍历整个数组来找到一个集合中的人的最小消费。
值得一提的是这道题的数据量较大，如果不优化并查集算法会时间超限，我这里只采用了比较简单的路径压缩优化，这个优化方法是每次在查找时，将查找的元素的父亲直接指向这个元素所在集合的代表，这样经过大量查找操作后，大多数元素都是直接指向它所在的集合的代表的，查找起来的时间复杂度也就成了O(1)。
#include <iostream>
#include <climits>
using namespace std;
int find_set(int * friends,int val) {//查
if(friends[val] == val)
return val;
friends[val] = find_set(friends, friends[val]);//路径压缩优化
return find_set(friends, friends[val]);
}
void union_set(int * friends,int x,int y) {//并
int xRoot = find_set(friends, x);
int yRoot = find_set(friends, y);
friends[xRoot] = yRoot;
}
int main() {
int peo,pair;
int l_operand,r_operand;
cin>>peo>>pair;
long long cost[peo];
int friends[peo + 1];
long long findCost[peo + 1];
// int find_index = 0;
for(int i = 0;i < peo;i++)
cin>>cost[i];
for(int i = 0;i <= peo;i++){
friends[i] = i; //建立集合的操作
findCost[i] = LONG_LONG_MAX;
}
while(pair--) {
cin>>l_operand>>r_operand;
union_set(friends, l_operand, r_operand);
}
for(int i = 1;i <= peo;i++) {
if(findCost[find_set(friends, i)] > cost[i - 1] ) {
findCost[find_set(friends, i)] = cost[i - 1];
}
}
long long res = 0;
for(int i = 0;i <= peo;i++) {
if(findCost[i] != LONG_LONG_MAX)
res += findCost[i];
}
cout<<res;
return 0;
}