刚刚接触并查集，有理解不当的地方，还望不吝指教。
先引入定义：并查集是一种树型的数据结构，用于处理一些不相交集合的合并问题。
最近在poj上做好好几道并查集的题目，个人感觉并查集的基本思路是这样的：通过合并使不相交集合之间产生关系，再利用查找方法来优化路径并更新集合中结点的信息。
一般方法
先定义结点类型
struct _node {
int parent;//必不可少，如有必要，可再添加其他属性
}NODE[length];
初始化方法
void Init(int n){
int i;
for(i=0;i<n;i++){
NODE[i].parent=i;
}
}
此时各结点单独构成不相交的集合。
查找方法
int Find(int index){
if(index==NODE[index].parent){
return index;
}else {
NODE[index].parent=Find(NODE[index].parent);
//如有必要，此时就对结点的相关属性进行更新
return NODE[index].parent;
}
}合并方法，注意，此时的操作是针对根结点的
void Unions(int x,int y){
int rx,ry;
rx=Find(x);
ry=Find(y);
NODE[rx].parent=ry;
//如果需要，对根结点进行相应的操作
}
以下是几道题的解题报告
POJ 1988 Cube Stacking
http://poj.org/problem?id=1988
这道题是并查集里面最简单也是最典型的题型
题意是大体是这样的，当输入M X Y时，就将X所在这一堆方块堆到Y所在的那一堆上；当输入C X时，就计算一下X下面有几个方块。以下是AC代码（作用GCC编译器）：
[b][color=red]#include <stdio.h>
struct point{
int parent;
int sum;
int ans;
}cube[100005];
void Init(int n){
int i;
for(i=1;i<=n;i++){
cube[i].parent=i;
cube[i].sum=1;
cube[i].ans=0;
}
}
int Find(int index){
int temp;
if(index==cube[index].parent){
return index;
}else {
temp=cube[index].parent;
cube[index].parent=Find(cube[index].parent);
cube[index].ans+=cube[temp].ans;
return cube[index].parent;
}
}
void Unions(int rx,int ry,int x,int y){
cube[rx].parent=ry;
cube[rx].ans=cube[ry].sum;
cube[ry].sum+=cube[rx].sum;
}
int main(int argc, char *argv[])
{
int p,x,y,s;
char c;
scanf("%d",&p);
Init(30010);
while(p--){
scanf("\n%c",&c);
if(c=='M'){
scanf(" %d %d",&x,&y);
int rx,ry;
rx=Find(x);
ry=Find(y);
Unions(rx,ry,x,y);
}else if(c=='C'){
scanf(" %d",&s);
Find(s);
printf("%d\n",cube[s].ans);
}
}
return 0;
}[/color][/b]解释一下：
struct point{
int parent;
int sum;
int ans;
}cube[100005];
每一个结点有三个属性值：根结点，所在堆的总方块数，以及它下面的方块数。由此可以很简单的推出初始化方法
void Init(int n){
int i;
for(i=1;i<=n;i++){
cube[i].parent=i;//集合独立
cube[i].sum=1;//总方块数为1
cube[i].ans=0;//下面没有方块
}
}
先说合并方法
void Unions(int rx,int ry,int x,int y){
cube[rx].parent=ry;
cube[rx].ans=cube[ry].sum;
cube[ry].sum+=cube[rx].sum;
}
在合并时，令下面那一堆的根结点为新堆的根结点。此时，X堆的根结点下面的方块数就为Y堆原来的总方块数，新堆的总数为两堆总数之和。
int Find(int index){
int temp;
if(index==cube[index].parent){
return index;
}else {
temp=cube[index].parent;
cube[index].parent=Find(cube[index].parent);
cube[index].ans+=cube[temp].ans;
return cube[index].parent;
}
}
只需要解释cube[index].ans+=cube[temp].ans ，在合并之后，结点的ans值并没有因此而改变，所以应该在Find方法里进行更新，此时结点下面的方块数应该是它原来的方块数加上它本来的根结点的方块数。
此题是入门题目，所以讲得有点详细。。。
POJ 1611 The Suspects
http://poj.org/problem?id=1611
AC 源代码（GCC你懂的）
[color=red][b]#include <stdio.h>
struct _node{
int parent;
}suspect[30000];
void Init(int n){
int i;
for(i=0;i<n;i++){
suspect[i].parent=i;
}
}
int Find(int index){
int temp;
if(index!=suspect[index].parent){
suspect[index].parent=Find(suspect[index].parent);
}
}
void Unions(int x,int y){
int rx,ry;
rx=Find(x);
ry=Find(y);
suspect[ry].parent=rx;
}
int main(int argc, char *argv[])
{
int n,m,num,id1,id2,group0,i,j,sum;
for(scanf("%d %d",&n,&m);n!=0;scanf("%d %d",&n,&m)){
Init(n);
getchar();
if(n==0 && m==0){
return 0;
}
for(i=0;i<m;i++){
scanf("%d %d",&num,&id1);
for(j=1;j<num;j++){
scanf("%d",&id2);
Unions(id1,id2);
}
getchar();
}
group0=Find(0);
sum=0;
for(i=0;i<n;i++){
if(Find(i)==group0){
sum++;
}
}
printf("%d\n",sum);
}
return 0;
}[/b][/color]
1703 Find them, Catch them
http://poj.org/problem?id=1703
题意是这样的，有两伙人，当输入D X Y的时候，表示X Y不在一伙，当输入A X Y时，判断X Y是否是一伙的，输入相应的"In the same gang.", "In different gangs." and "Not sure yet."。
[b]#include <stdio.h>
struct _node{
int parent;
int gang;//0表示与根结点是一伙的，1表示不是一伙的
}NODE[100010];
void Init(){
for(i=0;i<100010;i++){
NODE[i].parent=i;
NODE[i].gang=0;
}
}
/*蓝色字部分可以简化为NODE[n].gang=NODE[temp].gang==0?NODE[x].gang:(NODE[temp].gang+1)%2;思路是这样的，如果它原来的根结点与现在的根结点是一样的，那么它的gang值就不用改变，如果不是，那么要让它成为另外一伙的。当然(NODE[temp].gang+1)%2与1-NODE[temp].gang的处理是等价的，但前者应用起来更有普适性。*/
int Find(int n){
int temp;
if(n!=NODE[n].parent){
temp=NODE[n].parent;
NODE[n].parent=Find(NODE[n].parent);
[color=blue]if(NODE[n].gang==0){
NODE[n].gang=NODE[temp].gang;
}else{
NODE[n].gang=(NODE[temp].gang+1)%2;
}
}[/color] return NODE[n].parent;
}
/*
黄字部分是这样推出来的：如果NODE[x].gang==NODE[y].gang==0,说明x与rx一伙，y与ry一伙，但是x,y不是一伙的，所以令NODE[ry].gang=1;都等于1时也一样。同理，NODE[x].gang与NODE[y].gang不相等时，要令NODE[ry].gang=0;
*/
void Unions(int x,int y){
int rx,ry;
rx=Find(x);
ry=Find(y);
NODE[ry].parent=rx;
[color=yellow]NODE[ry].gang=(NODE[x].gang==NODE[y].gang)?1:0;[/color]}
//主函数就不用解释了吧。。
int main(int argc, char *argv[])
{
int t,n,m,a,b;
char c;
scanf("%d\n",&t);
while(t--){
scanf("%d %d\n",&n,&m);
Init();
while(m--){
scanf("%c %d %d",&c,&a,&b);
getchar();
if(c=='D'){
Unions(a,b);
}else if(c=='A'){
int rx,ry;
rx=Find(a);
ry=Find(b);
if(rx!=ry){
printf("Not sure yet.\n");
}else{
if(NODE[a].gang!=NODE[b].gang){
printf("In different gangs.\n");
}else{
printf("In the same gang.\n");
}
}
}
}
}
return 0;
}[/b]
POJ 1182 食物链
http://poj.org/problem?id=1182
这道题是中文题，题意就自己看吧。。
这道题的公式推起来是最麻烦的。先看代码
[color=red]#include <stdio.h>
struct point{
int parent;
int kind;
}ufind[50010];
void Init(int n){
int i;
for(i=0;i<n;i++){
ufind[i].parent=i;
ufind[i].kind=0;
}
}
int Find(int index){
int temp;
if(index==ufind[index].parent){
return index;
}else{
temp=ufind[index].parent;
ufind[index].parent=Find(ufind[index].parent);
ufind[index].kind=(ufind[temp].kind+ufind[index].kind)%3;
/*
上面这句话是这样推出来的。[img]
[img]http://dl.iteye.com/upload/attachment/482883/568157c8-19bf-3e3d-a7e8-dac6576528fa.png[/img]
[/img]如果原根结点与现在的根结点同类，而此结点与原根结点是同类的，那么他现在的类型还是0.如果此结点吃原根结点，那么他还是吃现在的根结点。如果它被原根结点吃，那么他还是被现在的结点吃。同理可推出上表的关系，从而推出ufind[index].kind=(ufind[temp].kind+ufind[index].kind)%3;
*/
return ufind[index].parent;
}
}
void Unions(int rootx, int rooty, int x, int y, int d)
{
ufind[rooty].parent=rootx;
ufind[rooty].kind=(-(d-1)+(ufind[x].kind-ufind[y].kind)+3)%3;
/*
上面的公式是这样推出来的，先根据d的值分类讨论，如果d为1的话，那么y的类型要设为x的类型,而rooty的类型就设为|x.kind-y.kind|;如果d为2的话，那么y的类型应该是(x.kind-1+3)%3,而rooty的类型还要在此基础上加上|x.kind-y.kind|;综上，可得到ufind[rooty].kind=(-(d-1)+(ufind[x].kind-ufind[y].kind)+3)%3;
*/
}
int main(){
int n,k,d,x,y,sum=0,rx,ry;
scanf("%d %d",&n,&k);
Init(n);
while(k--){
scanf("%d %d %d",&d,&x,&y);
//当前的话中X或Y比N大，就是假话；
if(x>n||y>n){
sum++;
}else
//当前的话表示X吃X，就是假话。
if(d==2 && x==y){
sum++;
}else {
rx=Find(x);
ry=Find(y);
if(rx!=ry){
Unions(rx,ry,x,y,d);
}
//当前的话与前面的某些真的话冲突，就是假话；
else{
if(d==1 && ufind[x].kind!=ufind[y].kind)
sum++;
if(d==2 && (ufind[x].kind-ufind[y].kind+3)%3!=1)
sum++;
}
}
}
printf("%d\n",sum);
return 0;
}[/color]
- 大小: 2.2 KB
分享到：
相关推荐
并查集是一种用于处理一些不交集的合并及查询问题的数据结构，在算法竞赛以及实际问题求解中有着广泛的应用。并查集的核心功能包括：创建集合（make_set）、查找元素所在集合（find_set）、合并两个集合（union_set...
并查集是一种在图论和算法设计中常用的离散数学结构，主要用于处理一些不相交集合的合并与查询问题。这个压缩包文件“团伙数据”显然包含了一些与并查集算法相关的练习数据和可能的题解，目的是帮助学习者更好地理解...
并查集（Union-Find Set）是一种用于管理分组的数据结构，它具备两个操作：(1) 查询元素a和元素b是否为同一组 (2) 将元素a和b合并为同一组。并查集的实现使用树形结构，使用树形结构来表示以后，每一组都对应一棵树...
### 并查集模版详解 #### 一、并查集简介 并查集是一种用于处理元素集合的动态数据结构，常被应用于图论、计算机网络、数据挖掘等领域。其核心功能是支持两种操作：合并两个集合（并操作）与查询某个元素所属的...
并查集是一种在分散的数据元素中寻找连接关系的数据结构，常用于处理一些不相交集合的合并与查询问题。在图论中，它可以帮助我们快速判断两个节点是否属于同一个连通分量，或者将两个连通分量合并。在本教程中，我们...
总结来说，经典并查集是一种高效的数据结构，适用于处理集合合并与查询问题。通过路径压缩和按秩合并等优化手段，可以在保持集合不相交性的前提下，提供高效的查找和合并操作，尤其在处理图论、网络流、社交网络等...
### 并查集C/C++代码实现 #### 知识点概述 并查集是一种用于处理元素集合的动态集合问题的数据结构，它支持两种基本的操作：**并**和**查**。并查集的主要用途是判断一个元素是否属于某个集合，并且能够有效地将两...
并查集是一种在图论和算法设计中常用的离散数据结构，主要应用于处理不相交集合的联合与查询问题。在ACM（国际大学生程序设计竞赛）中，它经常被用来解决各种组合优化和图论问题。下面我们将深入探讨并查集的核心...
### 并查集算法思想详解 #### 一、并查集基本概念 并查集是一种数据结构，主要用于处理一些不交集的合并及查询问题，它支持两种操作： 1. **合并**（Union）：将两个不同的集合合并成一个集合。 2. **查找**...
### C++ 实现并查集 #### 概述 并查集是一种树形的数据结构，常用于处理一些不交集的合并及查询问题，可以高效地进行集合的合并与查找操作。本文将介绍如何用C++语言实现一个简单的并查集，并通过具体的代码示例来...
总结，本篇精讲介绍了并查集这一数据结构的基本概念、核心算法以及Java实现，并通过两个实例展示了其在实际问题中的应用。并查集是解决离散集合操作的有效工具，尤其在处理大量查询和合并操作时，其高效性能使其成为...
总结来说，並查集是一种高效的数据结构，用于处理集合的合并与查询问题，它的核心操作包括查找和合并，并通过路径压缩和按秩合并等策略来优化性能。在实际应用中，並查集能很好地解决许多无向图的连通性问题。
总结起来，通过并查集这一数据结构，我们可以有效地处理集合的合并与查询，特别是在需要高效处理动态集合分组的问题中，如《银河英雄传说》中的战舰队列管理。并查集的优化技巧，如启发式合并和路径压缩，使得其在...
### 并查集在信息学竞赛中的拓展应用详解 #### 一、并查集简介及其在信息学竞赛中的角色 并查集（Disjoint Set Union, DSU）是一种用于处理一些不交集的合并及查询问题的数据结构。它主要用于解决元素集合的划分...
总结来说，本文详细介绍了并查集的基本概念、操作以及路径压缩这一优化策略，并结合给定的标题和描述推测了可能的编程题目类型。在实际应用中，理解并熟练掌握并查集及其优化方法对于解决涉及集合关系的问题至关重要...
根据给定的信息，本文将详细解释“POJ 1988 简单并查集”中的核心知识点，包括并查集的基本概念、代码实现以及在本题中的具体应用。 ### 并查集基本概念 并查集是一种用于处理一些不交集的合并及查询问题的数据...
并查集（Union-Find）是一种用于处理连接关系的数据结构...总结来说，理解并查集的关键在于掌握查找和合并操作的实现以及优化策略。在实际问题中，合理运用并查集能够有效解决涉及集合连接的问题，提高算法的运行效率。