正文

并查集并查集

Vincent丶  Vincent丶  2022-09-22  517

关键词：

本文参考了《挑战程序设计竞赛》和Jennica的github题解代码

模板

数组版：

int parent[MAX_N];
int rank[MAX_N];

void Init(int n){
	for(int i = 0; i < n; ++i){
		parent[i] = i;
		rank[i] = 0;
	}
}

int Find(int x){
	if(parent[x] = x){
		return x;
	} else {
		return Find(parent[x]);
	}
}

void Union(int x, int y){
	x = Find(x);
	y = Find(y);
	if(x == y)
		return;
	if(rank[x] < rank[y]){
		parent[x] = y;
	} else {
		parent[y] = x;
		if(rank[x] == rank[y]) rank[x]++;
	}
}

结构体版：

struct Node
{
    int rank;
    int parent;
 } node[MAX_N];

void Init(int n){
	for(int i = 0; i < n; ++i){
		node[i].parent = i;
		node[i].rank = 0;
	}
}

int Find(int x){
	if(node[x].parent = x){
		return x;
	} else {
		return Find(node[x].parent);
	}
}

void Union(int x, int y){
	x = Find(x);
	y = Find(y);
	if(x == y)
		return;
	if(node[x].rank < node[y].rank){
		node[x].parent = y;
	} else {
		node[y].parent = x;
		if(node[x].rank == node[y].rank) node[x].rank++;
	}
}

例题

例1 POJ 1182（带权并查集/种类并查集）

解题思路：

　　这个题是非常经典的并查集问题（种类并查集）。并查集作用：查询a和b是否属于同一组；合并a和b所在的组。注意并查集无法进行分割操作。利用题目中动物之间的相对关系可以建立一个并查集。对每一个元素，把它对父节点的关系用数组rank[i]表示，即relation，作为权值。0：与父节点同类 1：吃父节点 2：被父节点吃。

　　路径压缩。为了使查找效率提高，我们需要使树的高度尽可能小，让它只有一层，即在查找的过程中，把树中一条路径上的所有点都连在根节点上，从而加快了查找速度，与此同时，还要更新与此节点有关的其他变量，比如此节点与父节点的权值（父节点变为根节点），该树的高度等等。对于此题来讲，就是要更新节点与父节点的关系，因为此节点的父节点已经变为根节点。那么这里如何推导出此节点与根节点的关系呢。假设此节点为x，其父节点为y，y的父节点为z。则：

               rank[x]   rank[y]    x与z的关系权值
		          0        0         0=(i + j)%3  
		          0        1         1=(i + j)%3  
		          0        2         2=(i + j)%3
		          1        0         1=(i + j)%3 
                  1        1         2=(i + j)%3 
                  1        2         0=(i + j)%3 
                  2        0         2=(i + j)%3 
                  2        1         0=(i + j)%3 
                  2        2         1=(i + j)%3

　　推导公式：rank[x] = (rank[x] + rank[y]) % 3; 即对于i节点，更新公式为：rank[i] = (rank[i] + rank[parent[i]]) % 3。不过还有更简便的方法：模拟向量的运算x->z = x->y + y->z，所以rank[x] = （rank[x] + rank[y]）% 3。对3取模是为了保证结果为0,1,2。

　　最后是集合的合并操作。合并操作并不复杂，复杂的是更新集合间的关系（即集合根节点的关系）。这里有大神使用向量的形式来计算更新关系权值，假设需要合并x和y，查询得知x和y的根节点分别为：x_p，y_p，如果将x_p连接到y_p，那么rank[x_p]即为x_p与根节点y_p的关系。x_p->y_p = x_p->x + x->y + y->y_p = (-x->x_p + x->y + y->y_p)。所以更新公式为rank[x_p] = (-rank[x] + type - 1 + rank[y] + 3) % 3。（加上3是为了防止出现负数的情况；对3取模是为了保证结果的取值范围）。type即为输入的num。type为1，x与y同类，type为2，x吃y。

Solution：from 专注如一

#include <cstdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX_N = 50000 + 10;
int parent[MAX_N], rank[MAX_N];

void Init(int n){
    for(int i = 0; i <= n; ++i){
        parent[i] = i;
        rank[i] = 0;
    }
}

int Find(int x){
    if(parent[x] == x){
        return x;
    } 
    int y = Find(parent[x]);
    rank[x] = (ran[x] + ran[parent[x]]) % 3;
    return parent[x] = y;
}

int Union(int x, int y, int type){
    x_p = Find(x);
    y_p = Find(y);
    if(x_p == y_p){
        if((rank[x] - rank[y] + 3) % 3 == type - 1)
            return 0;
        return 1;
    }
    parent[x_p] = y_p;
    rank[x_p] = (-rank[x] + type - 1 + rank[y] + 3) % 3;
    return 0;
}

int main(){
    int n, k, res = 0;
    int type, x, y;
    scanf("%d %d", &n, &k);
    Init(n);
    for(int i = 0; i < k; ++i){
        scanf("%d %d %d", &type, &x, &y);
        if(x == y && type == 2)
            ++res;
        else if(x > n || y > n)
            ++res;
        else
            res += Union(type, x, y);
    }
    printf("%d\n", res);
    return 0;
}

　　此题还有一种解法。对于每只动物i创建3个元素i->A，i->B，i->C，并用这3*N个元素建立并查集。i->x表示动物i属于种类x；并查集里的每一个组内表示组内所有元素代表的情况都同时发生或不发生。例如i->A和y->B属于一组，那么就说明如果i属于A那么j一定属于B，相同的如果j属于B那么i一定属于A。

　　n = 1： x和y属于一类，那么合并x->A和y->A，x->B和y->B，x->C和y->C。

　　n = 2： x吃y 那么合并x->A和y->B，x->B和y->C，x->C和y->A。

　　另外要注意的是在合并之前要检查合并操作是否会产生矛盾。

Solution 2

#include <cstdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX_N = 50000 * 3 + 5;
//元素x，x + n，x + 2 * n分别代表x->A，x->B，x->C
int parent[MAX_N], rank[MAX_N];

void Init(int n){
    for(int i = 0; i <= n; ++i){
        parent[i] = i;
        rank[i] = 0;
    }
}

int Find(int x){
    if(parent[x] == x){
        return x;
    } 
    return parent[x] = Find(parent[x]);
}
bool same(int x, int y){
    return Find(x) == Find(y);
}
void Union(int x, int y, int type){
    x = Find(x);
    y = Find(y);
    if(x == y){
        return;
    }
    if(rank[x] < rank[y]){
        parent[x] = y;
    } else {
        parent[y] = x;
        if(rank[y] == rank[x]) rank[x]++;
    }
}

int main(){
    int n, k, res = 0;
    int type, x, y;
    scanf("%d %d", &n, &k);
    Init(n * 3);
    for(int i = 0; i < k; ++i){
        scanf("%d %d %d", &type, &x, &y);
        if(x == y && type == 2 || (x > n || y > n)){
            ++res; continue;
        } 
        if(type == 1){
            if(same(x, y + n) || same(x, y + 2 * n)){
                res++; continue;
            } else {
                Union(x, y);
                Union(x + n, y + n);
                Union(x + 2 * n, y + 2 * n);
            }
        } else {
            if(same(x, y) || same(x, y + 2 * n)){
                res++; continue;
            } else {
                Union(x, y + n);
                Union(x + n, y + 2 * n);
                Union(x + 2 * n, y);
            }
        }
    }
    printf("%d\n", res);
    return 0;
}

例2 POJ 2236

解题思路：

　　典型的并查集问题，较上一题简单。思路就是开辟两个数组，一个用来保存父节点，一个用来保存状态：是否被修复。假设现在修复电脑p，那么p状态就更改为已修复。然后在所有电脑中遍历一遍，只寻找满足以下条件的电脑：1. 已修复电脑（假设为q） 2. p和q 距离小于最大距离 3. p和q根节点不同（即不属于同一棵树），那么就合并p和q所在的树。查询是否可以通讯就很简单了，如果p和q的根节点相同，那么就可以通讯，否则通讯失败。这里要注意并查集不是只有一棵树，而是一个森林，包含了很多树。

Solution ：

#include <cstdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX_N = 1000 + 10;
int x[MAX_N], y[MAX_N];
int parent[MAX_N];
bool fixed[MAX_N];
int n, d;
bool close(int a, int b){
    return (x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] * y[b]) <= d * d;
}
void Init(int n){
    for(int i = 1; i <= n; ++i){
        parent[i] = i;
        fixed[i] = 0;
    }
}

int Find(int a){
    if(parent[a] == a){
        return a;
    } 
    return parent[a] = Find(parent[a]);
}

void Union(int a, int b){
    a = Find(a);
    b = Find(b);
    parent[a] = b;
}

int main(){
    scanf("%d%d", &n, &d);
    Init(n);
    for(int i = 1; i <= n; ++i){
        scanf("%d%d", &x[i], &y[i]);
    }
    char op[5];
    int a, b;
    while(scanf("%s", op) != EOF){
        if(op[0] == 'O'){
            scanf("%d", &a);
            if(!fixed[a]){
                fixed[a] = true;
                for(b = 1; b <= n; ++b){
                    if(!fixed[b]) continue;
                    if(Find(a) == Find(b)) continue;
                    if(close(a, b)){
                        Union(a, b);
                    }
                }
            }
        } else {
            scanf("%d%d", &a, &b);
            if(Find(a) == Find(b)){
                printf("SUCCESS\n");
            } else {
                printf("FAIL\n");
            }
        }
    }
    return 0;
}

例3 POJ 1703（种类并查集）

解题思路：

　　poj1182的简化版，模板一套就可以了。

Solution

例4 AOJ 2170

数据结构----并查集(代码片段)

并查集并查集概念并查集的模拟实现模拟实现并查集优化Union优化压缩路径循环递归并查集例题并查集概念并查集在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集... 查看详情

数据结构--并查集(代码片段)

并查集并查集原理并查集实现并查集原理在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要... 查看详情

数据结构并查集

并查集是一种数据结构，字面意思上来说，就是一个支持合并和查询的集合。并查集并查集的建立1voidinit()2{3for(inti=1;i<=n;i++)4{5father[i]=i;6}7}建立一个并查集很简单，只要开一个数组。这个数组储存某个节点对应的父节点编号。... 查看详情

数据结构----并查集(代码片段)

并查集并查集概念并查集的模拟实现模拟实现并查集优化Union优化压缩路径循环递归(深度过深有栈溢出的风险)并查集例题并查集概念并查集在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每... 查看详情

connectionsingalaxywarzoj-3261离线操作+逆序并查集并查集删边(代码片段)

#include<iostream>#include<cstring>#include<stdio.h>#include<map>#include<vector>#definecle(a)memset(a,0,sizeof(a))usingnamespacestd;constintN=50000+10;intw[20100];boolcmp(inta,intb)returna>b;intn,q,m,fa[N],arr[25000][2],ans[60000];vector<pair<int,int>>vp... 查看详情

树--12---并查集(代码片段)

文章目录并查集并查集是一种树型的数据结构并查集结构1.并查集的实现API设计UF(intN)构造方法实现union(intp,intq)合并方法实现代码：测试：案例1:计算机网诺连接2.UF_Tree算法优化eleAndGourp数组API设计find(intp)查询方法实现unio... 查看详情

[文文殿下]并查集详细解读(代码片段)

初探并查集并查集(Disjoint-Set)是一种优美的数据结构，它擅长动态维护若干交集为空的集合，并且支持快速合并两个集合以及查找某个元素所在的集合。然而这只是并查集所能做的一点微小的工作，文文对并查集的理解是“一种... 查看详情

并查集(代码片段)

并查集并查集是对树的一种操作，旨在找到某个节点的公共祖先（最老公共祖先）。我们先讲一下并。并并就是讲两个节点合并到一个集合里面（这个集合必须是树），每个节点对应一个祖先，最老公共祖先的祖先就是自己，而... 查看详情

数据结构（并查集）(代码片段)

并查集并查集是一种怎么样的数据结构呢？ 1.处理集合合并2.对集合元素进行查找同时并查集对集合元素进行查找的时候，会把路径上所有的点全部都指向父节点，这样就可以把整个查询工作近似的优化成o（1ÿ... 查看详情

数据结构（并查集）(代码片段)

并查集的基本操作和用法(代码片段)

并查集并查集的作用：1.合并区间2.判断两个数是否再同一个集合之中3.寻找联通子图的的个数并查集的关键函数find(x)与p[]数组寻找x的祖宗节点/* find函数用于寻找祖宗节点*/intfind(intx)if(p[x]!=x) find(p[x])returnp[x];/* p[N] 存储每... 查看详情

并查集的初步认识

...你他们是否有联系？如何快速解决这类问题，这时候需要并查集并查集意思是说，有个类似指针的东西，将子节点连接父节点，那么这个时候，父子节点是连接的，如果父节点是根节点，那么父节点的指针指向自己；这里让父节... 查看详情

并查集的基本操作和用法(代码片段)

❤️数据结构入门❤️（2-5）-并查集

文章目录一、并查集的定义二、并查集的图解三、并查集的实现1、并查集的插入2、并查集的删除3、并查集的修改4、并查集的查找四、并查集的刷题实战一、并查集的定义二、并查集的图解三、并查集的实现1、并查集的插入2、... 查看详情

p3295萌萌哒并查集rmq联动(代码片段)

...排列组合问题。有些限定条件，要相等的地方，我们就用并查集并起来。最后一查有多少个并查集，就有多少个位置可供自由选择。所以答案就是10^(并查集数)，去除前导0：*(9/10)好，这样我们得到了一个O(mn)算法。然后我们考虑... 查看详情

并查集模板(代码片段)

并查集并查集是数据结构中的一个重要算法，可以管理元素分组，并查集由三部分构成：初始化，找父节点，合并结点，直接来看并查集的模板：voidinit(intn)for(inti=1;i<=n;++i)fa[i]=i,ran[i]=0;//刚开始每个人都是自己的老大，每个人... 查看详情

并查集

并查集1.并查集是什么并查集是一种用来管理元素分组情况的数据结构。并查集可以高效地进行如下操作。不过需要注意并查集虽然可以进行合并操作，但是无法进行分割操作。查询元素a和元素b是否属于同一组。合并元素a和元... 查看详情