首页 > 其他分享 >并查集

并查集

时间:2024-08-14 19:17:25浏览次数:13  
标签:int fy 查集 ceng fx find

并查集(递归写法)

#include<bits/stdc++.h>
using namespace std;
const int X = 10010;
int f[X];
int n, m;	
//初始化
void init() {
	for (int i = 0; i < X; i++) {
		f[i] = i;
	}
}
//查找上级是谁
int find(int x) {
	if (x != f[x]) {
		return f[x] = find(f[x]);//路径压缩
		//相当于
		/*
		f[k]=find(f[k]);
        return f[k];
		*/
	}
	return f[x];
}
//合并
void join(int x, int y) {
	int fx = find(x), fy = find(y);
	if (fx != fy) {
		f[fy] = fx;
	}
}
//判断集合个数
bool check()
{
	int sum = 0;
	for (int i = 1; i <= n; i++)
	{
		if (f[i] == i) sum++;//统计独立集合的个数
		if (sum == 2) return 0;//发现有两个就返回false应该会省一点时间
	}
	return 1;//只有1个集合,返回true
}
int main() {
	init();
	cin >> n >> m;
	while (m--) {
		int t, x, y;
		cin >> t >> x >> y;
		if (t == 1) {
			join(x, y);
		}
		if (t == 2) {
			if (find(x) == find(y))
				cout << "Y" << endl;
			else
				cout << "N" << endl;
		}
	}
	return 0;
}

并查集(循环写法)

#include<bits/stdc++.h>
using namespace std;
const int X = 10010;
int f[X];
int ceng[X];
int n, m;
//初始化
void init() {
	for (int i = 0; i < X; i++) {
		f[i] = i;
		ceng[i] = 0;
	}
}
//查找上级是谁
int find(int x) {
	int i, j, k;
	k = x;
	while (k != f[k])
		k = f[k];
	i = x;
	while (i != k) {
		j = f[i];
		f[i] = k;
		i = j;
	}
	return k;
}
//合并
void join(int x, int y) {
	int fx = find(x), fy = find(y);
	if (ceng[fx] > ceng[fy])
		f[fy] = fx;
	else {
		if (ceng[fx] == ceng[fy])
			ceng[fy]++;
		f[fx] = fy;
	}
}
//判断集合个数
bool check()
{
	int sum = 0;
	for (int i = 1; i <= n; i++)
	{
		if (f[i] == i) sum++;//统计独立集合的个数
		if (sum == 2) return 0;//发现有两个就返回false应该会省一点时间
	}
	return 1;//只有1个集合,返回true
}	
int main() {
	init();
	cin >> n >> m;
	while (m--) {
		int t, x, y;
		cin >> t >> x >> y;
		if (t == 1) {
			join(x, y);
		}
		if (t == 2) {
			if (find(x) == find(y))
				cout << "Y" << endl;
			else
				cout << "N" << endl;
		}
	}
	return 0;
}

标签:int,fy,查集,ceng,fx,find
From: https://www.cnblogs.com/gaohaojie/p/18359615

相关文章

  • 【知识】并查集的单点删除 &【题解】SP5150
    \(\mathfrak{1st.}\)前言-->题目传送门<--原先这道题的难度是紫,我觉得题目翻译看不懂,就去讨论版发了个贴,然后题管更新了题目翻译,并且把难度降到了蓝……\(\mathfrak{2nd.}\)思路赶时间或嫌啰嗦的可以直接跳到『思路归纳』。我们先从普通并查集开始思考对于删除单点\(x\),......
  • 关于并查集
    关于冰茶姬简述冰茶姬是一种用于管理元素所属集合的数据结构,实现为一个森林,其中每棵树表示一个集合,树中的节点表示对应集合中的元素。顾名思义,冰茶姬支持两种操作:合并(Union):合并两个元素所属集合(合并对应的树)查询(Find):查询某个元素所属集合(查询对应的树的根节点),这可以用于......
  • P5836 [USACO19DEC] Milk Visits S(树上并查集)
    核心思路对于相同颜色且相邻的点合并。若不在同一集合,则0若在同一集合,同色1异色0AC代码#include<bits/stdc++.h>usingnamespacestd;intfa[1145141];charcol[1145141];intn,m;intfind(intx){ if(x==fa[x]) returnx; returnfa[x]=find(fa[x]);}v......
  • *算法训练(leetcode)第四十七天 | 并查集理论基础、107. 寻找存在的路径
    刷题记录*并查集理论基础107.寻找存在的路径*并查集理论基础讲解107.寻找存在的路径题目地址直接套模板。结点编号从1开始,因此定义father数组时需要n+1个空间,否则会越界。时间复杂度:O(......
  • 广场舞老太太都看得懂的并查集
    1.并查集为什么叫“并查集”这个名字?因为并查集它的主要用处就是并(合并无交集集合)和查(查找元素或判断是否有该元素),当然路径压缩也得用到它。话说回来,并查集虽然是图论里的东西,但是本身像个树。2.算法说到并查集,就不得不提到压缩路径了,它是一个超级简单,但是很牛的算法,算法主......
  • 为什么并查集路径压缩不需要维护rank?
    在基于rank进行优化的并查集中,路径压缩确实不需要维护rank数组。这是因为路径压缩和rank优化有不同的目的和作用机制。让我们详细解释一下原因:Rank优化的目的:Rank优化的主要目的是在合并两个集合时,让较小的树成为较大的树的子树,以保持树的平衡性。这样可以避免树变得过于深,从而......
  • 并查集详解
    并查集并查集是一种树形数据结构,用于处理一些不相交集合的合并及查询问题(即所谓的并、查)。具体详解见此并查集本身是真的太板了。。普及-以下的题基本全是板。直接见例题吧:板子一【模板】并查集题目描述如题,现在有一个并查集,你需要完成合并和查询操作。【】输入格式】第......
  • 数据结构 - 并查集路径压缩
    ......
  • 并查集
    并查集在每个集合中选择一个元素,作为整个集合的代表。使用一个树形结构存储每个集合,树上的每个节点都是一个元素,树根是集合的代表元素。存储时,记录每个节点\(x\)的父亲\(fa[x]\)。查询\(x\)和\(y\)是否在同一集合时,分别从两个点出发,寻找它们的树根。若树根相同,则说明\(......
  • 数据结构 - 并查集基础
    ......