首页 > 其他分享 >并查集和带权并查集原理分析

并查集和带权并查集原理分析

时间：2023-07-17 15:22:14浏览次数：39  
标签：fx return int 查集 fa 带权 集合 原理 find

并查集是算法竞赛中常用的一种数据结构。

它可以高效地处理集合之间的操作与询问。

其主要功能是查询两个元素是否在同一个集合以及将两个集合合并。

第一部分 并查集的基本操作

算法思想

  1. 我们将所有元素建成很多棵树（森林），每一棵树就是一个集合。

  2. 因为并查集是一个树结构，那么每个节点都有一个指针指向父节点。

image

  1. 最开始时，每个元素就是一个独立的集合，每个元素各为一棵树且自己就是根及自己指向自己。

image

  1. 当我们要查询两个元素是否在同一个集合时，可以判断它们是否在同一棵树上，即只要判断它们所在树的根相同与否就可以了。
    比如下图 \(2, 3\) 有相同的根 \(1\)，它们便在一个集合，但是 \(2, 9\) 分别拥有根 \(1, 7\)，不在同一个集合。

image

  1. 当我们要合并两个集合时，只要两棵树合并即可，即只要把两棵树的根节点连接起来就可以了。

image

算法优化（路径压缩）

我们发现，如果建出来的树长这样：

image

多次查找非常费时间，因为每次都可能要从最下面跑到最上面。

因为它们都是一个集合的，不在乎它在集合中的顺序或位置，所以我们可以把树变成这样：

image

即每次查询一个元素在哪一个集合的时候顺便把它接在根节点上。

下面我们通过例题讲讲如何实现该数据结构。

例题

例题1：HDU 1213 How many tables
题目描述

image

思路

认识的人合并为一个集合，最后查找有多少个集合即可。

查询集合数量有两种方法：

方法1：等所有操作进行完成以后，我们可以查询有多少棵树，也就是查找有多少个根；
方法2：我们定义 \(cnt\) 初始值为 \(n\)，当合并两个不同的集合时，\(cnt\) 就可以 \(-1\)，代表两个集合合并，集合数量少了一个。

代码
#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int n, m;
int fa[N];

void init() {
    for (int i = 1; i <= n; i++) fa[i] = i;
}

int find(int u) {
    if (u == fa[u]) return u;
    return fa[u] = find(fa[u]);
}

void merge(int a, int b) {
    int fx = find(a), fy = find(b);
    if (fx != fy) fa[fx] = fy;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        cin >> n >> m;
        int cnt = n;
        init();
        for (int i = 1; i <= m; i++) {
            int x, y;
            cin >> x >> y;
            if (find(x) != find(y)) cnt--;
            merge(x, y);
        }
        cout << cnt << '\n';
    }

    return 0;
}
例题2：P3958 [NOIP2017 提高组] 奶酪
题目描述

image

思路

如果两个圆的中心相距不超过 \(2R\)，\(R\) 为半径，那么就将两个洞合并为一个集合；

如果一个圆的中心与上下表面相距不超过 \(R\)，那么就将洞与上下表面合并；

最后看看上下表面受否在同一个集合，如果在同一个集合，那么一定可以从下走到上。

代码
#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int n;
double h, r;

struct pos {
    double x, y, z;
} p[N];

int fa[N];

int find(int x) {
    if (x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}

void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return;
    fa[fx] = fy;
}

double dis(int v1, int v2) {
    double x = p[v1].x, y = p[v1].y, z = p[v1].z;
    double a = p[v2].x, b = p[v2].y, c = p[v2].z;
    return sqrt((x - a) * (x - a) + (y - b) * (y - b) + (z - c) * (z - c));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        cin >> n >> h >> r;
        for (int i = 1; i <= n; i++) cin >> p[i].x >> p[i].y >> p[i].z;
        for (int i = 0; i <= n + 1; i++) fa[i] = i;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                if (dis(i, j) <= 2 * r) {
                    merge(i, j);
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            if (p[i].z <= r) merge(0, i);
            if (p[i].z >= h - r) merge(n + 1, i);
        }
        if (find(0) == find(n + 1)) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}
例题3：P1111 修复公路
题目描述

image

思路

我们将所有公路按照修复时间从小到大排序，然后一个一个合并过去，如果什么时候只有一个联通块时就是最少的时间。

代码
#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

struct road {
    int x, y, t;
} r[N];

int n, m;
int fa[N];

int find(int x) {
    if (x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}

int merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return 0;
    fa[fx] = fy;
    return 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= m; i++) cin >> r[i].x >> r[i].y >> r[i].t;
    sort(r + 1, r + m + 1, [](const road a, const road b) { return a.t < b.t; });

    int cnt = n;
    for (int i = 1; i <= m; i++) {
        int x = merge(r[i].x, r[i].y);
        cnt -= x;
        if (cnt == 1) {
            cout << r[i].t << '\n';
            return 0;
        }
    }
    cout << -1 << '\n';
    return 0;
}

第二部分 带权并查集

算法思路

即为树上的每一条边赋上一个权值，比如边的长度，维护该节点与父节点的关系。

相应的，当我们进行路径压缩的优化时，我们发现所有的节点都接到根上边去了，那么这时每一条边也自然而然地变成了维护该节点与根节点的关系。

比如权值是是长度时，我们要根据路径压缩的结果对路径权值进行更新：

image

路径压缩时更新权值

还是路径长度的例子（如上图），

当我们的父节点 \(f\) 已经被成功合并到根节点时，

我们自然而然地想到如何更新子节点 \(x\) 的距离信息，

看下面的图可以帮助理解

有 \(d[x] = d[x_原] + d[f]\)，

\(d[x_原]\) 表示 \(x\) 节点与原来的父节点的距离，

现在的 \(x\) 的父节点变成了根，我们可以想到上面的公式。

image

合并时更新权值

假如给定 \(x\) 点和 \(y\) 点的距离为 \(v\)，

然后我们要将 \(x\) 所在集合和 \(y\) 所在集合合并，

如何处理呢？

我们把 \(x\) 树接到 \(y\) 上，

image

更新父节点的方式还是 \(fa[rx] = ry\)，

我们发现只有一条边发生改变，就是图中标红的边（\(d[rx]\)）：

image

\(d[rx]\) 被更改了，

其他边都可以随着调用上面讲的 \(find\) 函数进行更新。

怎么更新 \(d[rx]\) 呢，

我们可以利用高中数学知识（向量）去理解，

容易发现 \(d[rx] = -d[x] + v + d[y]\)。

image

这里举的是路径长度的问题，在遇到各种题目时中可以灵活运用，将 \(+\) 改成 \(\times -\) 等。

例题

例题4：HDU3038 How Many Answers Are Wrong
题目描述

image

思路

对于一个区间 \([l, r]\) 的和为 \(s\) 我们可以这样理解：\(l - 1\) 和 \(r\) 的差距为 \(s\)。

我们能想到这一点就非常简单了，把刚刚的 \(a, b\) 两点的路径长度改成 \(l - 1\) 和 \(r\) 相差 \(s\) 即可。

直接套用模板。

代码
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200010;

int n, m;
int fa[N];
int d[N];
int ans;

void init() {
	ans = 0;
	for (int i = 0; i <= n; i++) fa[i] = i, d[i] = 0;
}

int find(int u) {
	if (u == fa[u]) return u;
	int f = fa[u];
	fa[u] = find(fa[u]);
	d[u] += d[f];
	return fa[u];
}

void merge(int x, int y, int v) {
	int fx = find(x), fy = find(y);
	if (fx == fy) {
		if (d[y] - d[x] != v) {
			ans++;
		}
	}
	else {
		fa[fy] = fx;
		d[fy] = -d[y] + v + d[x];
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	while (cin >> n >> m) {
		init();
		for (int i = 1; i <= m; i++) {
			int l, r, s;
			cin >> l >> r >> s;
			merge(l - 1, r, s);
		}
		cout << ans << '\n';
	}
	return 0;
}
例题5：POJ1703 Find them, Catch them
题目描述

题目翻译出来有很多种，有说吃糖的，有说警察抓小偷的。。。

image

思路

一样的道理，如果一个节点 \(x\) 与父节点的糖的类型相同，那么 \(d[x] = 0\)，如果不同 \(d[x] = 1\)。

对于第一种操作 D a b ，我们只要知道 \(x\) 点和 \(y\) 点的关系为 \(1\) 即可。

对于第二种操作 A a b，我们只要知道 \(x\) 点和 \(y\) 点与根节点的关系是否相同即可。

代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int d[N];
int fa[N];

void init() {
    for (int i = 0; i <= n; i++) fa[i] = i, d[i] = 0;
}

int find(int x) {
    if (x == fa[x]) return x;
    int f = fa[x];
    fa[x] = find(fa[x]);
    d[x] += d[f];
    return fa[x];
}

void merge(int x, int y, int v) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return;
    fa[fx] = fy;
    d[fx] = -d[x] + v + d[y];
}

int mod(int x, const int m) {
    return (x % m + m) % m;
}

void solve() {
    scanf("%d%d", &n, &m);
    init();
    char opt[2];
    int a, b;
    for (int i = 1; i <= m; i++) {
        scanf("%s%d%d", opt, &a, &b);
        if (*opt == 'A') {
            int fa = find(a), fb = find(b);
            if (fa != fb) printf("Not sure yet.\n");
            else if (mod(d[a] - d[b], 2) == 0) printf("In the same gang.\n");
            else printf("In different gangs.\n");
        }
        else {
            merge(a, b, 1);
        }
    }
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}
例题6：P1525 [NOIP2010 提高组] 关押罪犯
题目描述

image

思路

我们将所有的关系看成边，所有的犯人看成点，将边按照怒气值从大到小排序。

利用贪心，我们从前往后枚举，那么越靠前的怒气值越大，我们越不希望将其保留下来，我们更希望将他们放进两个监狱。

于是我们套路化地将那两个犯人连上一条权值为 \(1\) 的边，表示他们最好呆在两个监狱。

当什么时候发生矛盾时，那么那个边的怒气值就是答案，也是省长会看到的值。

代码
#include <bits/stdc++.h>

using namespace std;

const int N = 20010, M = 100010;

struct edge {
    int u, v, w;
} e[M];

bool cmp(const edge a, const edge b) {
    return a.w > b.w;
}

int n, m;

int fa[N];
int d[N];

int mod(int x, const int m) {
    return (x % m + m) % m;
}

int find(int x) {
    if (x == fa[x]) return x;
    int f = fa[x];
    fa[x] = find(fa[x]);
    d[x] = mod(d[x] + d[f], 2);
    return fa[x];
}

bool merge(int x, int y, int v) {
    int fx = find(x), fy = find(y);
    if (fx == fy) {
        if (mod(d[x] - d[y], 2) != v) {
            return false;
        }
    }
    else {
        fa[fx] = fy;
        d[fx] = mod(-d[x] + v + d[y], 2);
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= m; i++) cin >> e[i].u >> e[i].v >> e[i].w;
    sort(e + 1, e + m + 1, cmp);

    for (int i = 1; i <= m; i++) {
        if (!merge(e[i].u, e[i].v, 1)) {
            cout << e[i].w << '\n';
            return 0;
        }
    }
    cout << 0 << '\n';
    return 0;
}
例题7：P1196 [NOI2002] 银河英雄传说
题目描述

image

思路

这次权值维护方法的不太一样。

我们将一列的战舰当作一个集合，

通过并查集维护集合和每一个点 \(u\) 到根节点的距离 \(dis[u]\)，

调查同一个集合的 \(u, v\) 相差多少个战舰可以通过 \(|dis[u] - dis[v]| - 1\) 算出；

合并 \(x\) 到 \(y\) 时，注意修改 \(dis[x]\) 为 \(y\) 树原来的大小，\(y\) 树的大小要加上 \(d[x]\)。

代码
#include <bits/stdc++.h>

using namespace std;

const int N = 30010;

int fa[N];
int sz[N];
int d[N];

void init() {
    for (int i = 1; i < N; i++) fa[i] = i, sz[i] = 1, d[i] = 0;
}

int find(int x) {
    if (x == fa[x]) return x;
    int f = fa[x];
    fa[x] = find(fa[x]);
    d[x] += d[f];
    return fa[x];
}

void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return;
    fa[fx] = fy;
    d[fx] = sz[fy];
    sz[fy] += sz[fx];
}

int query(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx != fy) return -1;
    return max(0, abs(d[x] - d[y]) - 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    init();
    int T;
    cin >> T;
    char opt;
    int x, y;
    while (T--) {
        cin >> opt >> x >> y;
        if (opt == 'M') merge(x, y);
        else cout << query(x, y) << '\n';
    }

    return 0;
}

标签：fx,return,int,查集,fa,带权,集合,原理,find
From： https://www.cnblogs.com/PlayWithCPP/p/17560209.html

相关文章

  • 一文搞懂数据库索引原理
    前言写数据库，我第一时间就想到了MySQL、Oracle、索引、存储过程、查询优化等等。不知道大家是不是跟我想得一样，我最想写的是索引，为啥呢？以下这个面试场景，不知道大家熟悉不熟悉：面试官：数据库有几千万的数据，查询又很慢我们怎么办？面试者：加索引。面试官：那索引有哪些数据类型？索引是......
  • spring启动流程 (5) Autowired原理
    构造方法参数AutowireBeanClass可以在构造方法上标注@Autowired注解，Spring在创建Bean实例时将自动为其注入依赖参数Spring会优先使用标注@Autowired注解的构造方法当一个构造方法标注了@Autowired注解且required=true时，其余构造方法不允许再标注@Autowired注解当多个构造方法......
  • 概述 - 核心原理
    本书从实际需求出发，全面并且细致地介绍了有关高并发编程的基础知识、核心原理、实战案例和系统架构的相关知识。「基础篇」：介绍了操作系统线程调度的相关知识和并发编程的基础知识。操作系统线程调度的知识包含：冯诺依曼计算机模型、CPU架构、操作系统线程和Java与操作系统线程的......
  • [笔记]组成原理_计算机系统概述
    计算机系统的层次结构硬件和软件系统共同构成了一个完整的计算机系统。冯·诺依曼机的基本思想——“存储程序”其特点如下：采用存储程序的工作方式。计算机硬件系统由运算器、存储器、控制器、输入设备和输出设备五大部件组成。指令和数据以同等地位存储在存储器中，形式上没......
  • 容器原理之cgroup
    “以docker为代表，轻量、便携的container使得打包和发布应用非常容易。系列文章容器原理主要分析container用到的核心技术，主要包括Linuxnamespace，cgroups，overlayfs，看完这些内容，你将可以手动创建一个和container类似的环境。cgroup（controlgroup）是一个内核特性，用于限......
  • [笔记]组成原理_输入/输出系统
    I/O接口I/O接口的功能IO接口的主要功能有：进行地址译码和设备选择。（CPU送来选择外设的地址码后，接口必须对地址进行译码，以产生设备选择信息，使主机能和指定外设交换信息。）实现主机和外设的通信联络控制。（解决主机与外设时序配合问题，协调不同工作速度的外设和主机之间交换信息，以......
  • 08、MVCC原理
    本篇内容主要来源于自己学习的视频，如有侵权，请联系删除，谢谢。1、什么是MVCCMVCC（Multiversionconcurrencycontrol）是一个基于多版本技术实现的一种并发控制机制。常见的并发机制有哪些？MVCC的优点在哪里呢？比如数据库中的悲观锁，也就是通过锁机制确保同一时刻只能有一个事务......
  • 高并发的哲学原理（七）-- 最难以解决的单点：数据库以及它背后的存储
    前面六篇文章，我们解决了web服务的百万QPS问题，从本文开始，我们将用三篇文章，尝试构建出百万QPS后端系统所需要的数据库。首先要明确，这里的数据库指的是关系型数据库，即满足ACID原则并用SQL语言进行操作的持久性（掉电数据不丢）数据库。当然，在追求高并发的过程中，我们将不可避免......
  • 高并发的哲学原理（八）-- 将 InnoDB 剥的一丝不挂：B+ 树与 Buffer Pool
    前面几篇文章，我们大多数时候都在挥舞着架构大棒，对性能问题进行降维打击，但是本文不一样，本文要啃硬骨头：吃透MySQL的InnoDB存储引擎，以便于我们能顺利地看懂下一篇文章。同时，本文也是一篇比较完善的讲解InnoDB底层设计原理的文章，单独作为InnoDB的一篇详解文章我认为也是极好......
  • linux 内存管理 --- 用户空间 malloc 内存申请原理
    相对于栈而言，堆这片内存面临着一个稍微复杂的行为模式：在任意时刻，程序可能发出请求，要么申请一段内存，要么释放一段已经申请过的内存，而且申请的大小从几个字节到几个GB都有可能，我们不能假设程序一次申请多少堆空间，因此，堆的管理显得较为复杂。那么，使用malloc()在堆上分配内存到底是......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99