C++并查集——通过一道实例说明
并查集在对待某一类问题时十分有效。
能够方便解决联通性的问题。
通过一道题目实例说明：
小Y到岛上淘金，湖中共有N个小岛，每个小岛上都有若干个金币
岛与岛之间有桥连接，一共有M座桥，小Y不会游泳，所以他只能通过桥访问其他的小岛
但是小Y为了淘金，找万能的魔法师小L要来了两颗传送卷轴，传送卷轴可以让他移动到另外一个小岛（无论是否之间是否有桥相连）
1号岛是大陆，小Y起初站在1号岛上，小Y访问完小岛之后会回到1号岛，毕竟他不想流落荒岛变成野人
小Y最多可以获得多少个金币
输入
n m
W1 W2 ... Wn
A1 B1
A2 B2
...
Am Bm
上面W1到Wn表示每座岛有多少个金币
接下来m对数字
每对数字表示哪两个岛之间有一座桥
注意桥是双向的，并且可能两座岛之间会有多座桥
桥可以无限次重复走
输出
最多的金币数目
样例输入
5 4
1 1 3 4 10
1 2
2 1
3 4
4 3
样例输出
12
提示
直观解决的思路非常简单：
连起来的岛都归到一块
跟1号岛相连的岛的金币加上 除此外连接起来的岛的金币 之和即为最终答案
10为传送到达
问题的核心在于如何快速的将这些岛分到一块。
即点的联通问题。
来看具体实现
//pre用于存其上一个连接的地方，pre[i] == i则代表为根节点
//w与此题相关
int pre[1000],w[1000],root[1000]={0};
//查找函数，查找它的根结点
intfind_root(int x){
int r = x;
//查找根节点
while(r != pre[r])
r = pre[r];
//以下是并查集的路径缩短，能够节约时间以及防止一些极端情况如一串相连
int t;
while(x != pre[x]){
t = pre[r];
pre[x] = r;
x = t;
}
return r;
}
//连接操作
void join(intx,int y){
int fx = find_root(x),fy = find_root(y);
//判别根节点是否一样，即大家本来在不在一块
//不在则使其中一个根结点连接在另一个上
if(fx!=fy){
pre[fy] = fx;
}
}
int main()
{
scanf("%d%d",&N,&M);
//initialize the pre
//初始化pre数组，一开始都没有相连，所以为其自身
//0或者1依据情况使用
for(int i = 1;i<=N;i++){
pre[i] = i;
scanf("%d",&w[i]);
}
//join
while(M){
int x,y;
//输入连接
scanf("%d%d",&x,&y);
join(x,y);
M--;
}
int max_n = 0;
//将所有多并行连接改到一个根结点连接
//因为在使用join查找时有可能会出现上面一张所示并非单层相连的场景。
for(int i = 1;i<=N;++i)
find_root(i);
//可以通过判别pre[i] 是否等于i判别该点是否为根结点
//最终在一块的都会加到同一方位root[]中
//后面与该题相关
for(int i = 1;i<=N;i++){
root[pre[i]] +=w[i];
}
for(int i = 1;i<=N;i++){
if(i == pre[1]) continue;
if(root[i] > max_n) max_n = root[i];
}
cout<<(root[pre[1]]+max_n)<<endl;
}
