首页 > 其他分享 >蓝桥杯-并查集-合根植物

蓝桥杯-并查集-合根植物

时间:2024-04-12 17:13:34浏览次数:29  
标签:合根 int 查集 蓝桥 init Maxn find

0.题目

1.解析

1.1 并查集

思路

主要三大模板功能 1.初始化(init) 2.寻找父节点(find) 3.合并(merge)
我们在find中可以使用路径压缩简化运算,缩短运行时间
而启发式合并则可以将运行时间压缩,由O(n)到 o(logn)

代码

#include<bits/stdc++.h>
using namespace std;
const int Maxn = 1e6 + 10;
int fa[Maxn+1]; // 记录父节点 
int sz[Maxn+1]; // 记录树的大小 
int m, n, k; 
// 初始化操作 
void init(){
	for(int i = 1; i <= Maxn; i++){
		fa[i] = i;	
		sz[i] = 1; 
	}	
}

// 寻找父节点(DFS递归) 
//int find(int x){
//	// 找到根节点 
//	if(x == fa[x]){
//		return x;
//	}
//	// 没有找到,继续向前DFS递归 
//	else{
//		return find(fa[x]);
//	} 
//}

// 寻找父节点(路径压缩) 
int find(int x){
	// 找到根节点 
	if(x == fa[x]){
		return x;
	}
	// 没有找到,继续向前DFS递归 
	else{
		fa[x] = find(fa[x]); 
		return fa[x];
	} 
}



// 合并操作(根节点合并)
//void merge(int x, int y){
//	fa[find(x)] = find(y);
//}

void merge(int x,int y)//启发式合并
{
    x=find(x);
    y=find(y);
    if(x!=y)
    {
        if(sz[x]<sz[y])
            swap(x,y);
        sz[x]+=sz[y];
        fa[y]=x;
    }
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;
	init(); 
	for(int i = 0; i < k; i++){
		int a, b;
		cin >> a >> b; 
		merge(a, b);
	}
	
	int ans = 0;
	for(int i = 1; i <= n*m; i++){
		if(fa[i] == i){
			ans++;
		}
	}
	cout << ans;
	return 0;
}

标签:合根,int,查集,蓝桥,init,Maxn,find
From: https://www.cnblogs.com/trmbh12/p/18131686

相关文章

  • 2023蓝桥杯 java A组 小蓝的旅行计划
    最小堆(优先队列)和区间树(线段树,红黑树)的结合java中有自己实现这两种数据结构的对象(1)最小堆(优先队列)PriorityQueue<int[]>minHeap=newPriorityQueue<>(newComparator<int[]>(){//int[]三个元素第一个cost第二个lim第三个tag @Override publicintcompare(int......
  • [蓝桥杯 2022 省 A] 爬树的甲壳虫
    概率dp,关键是要走出思维定势:一般来讲,都会把dp[i]定义为从0爬到高度i的概率,但是因为任何时刻都有掉下去的可能,这样子不好推(也有大佬这样做出来的)我们把dp[i]定义为从i爬到n的概率,公式就好推了而且,我们可以根据定义很自然地得到:dp[n]=0#include<bits/stdc++.h>usingnamespa......
  • 蓝桥杯-构造(数学公式1/n = 1/(n+1) + 1/(n+1)n )
    0.题目1.题解1.0找规律n=1,1/1=1/2+1/3+1/6n=2,1/2=1/4+1/6+1/12n=3,1/3=1/6+1/9+1/18....实际上,1/6=1/12+1/12,1/12=1/36+2/36=1/36+1/18即1/6=1/(62)+1/(623/2)+1/(623),即2,3,6三种1.1构造我们想要知道1/n......
  • 2022年蓝桥杯C++B组国赛-试题D-最大数字
    0.题目问题描述给定一个正整数N。你可以对N的任意一位数字执行任意次以下2种操作:将该位数字加1。如果该位数字已经是9,加1之后变成0。将该位数字减1。如果该位数字已经是0,减1之后变成9。你现在总共可以执行1号操作不超过A次,2号操作不超过......
  • 蓝桥杯-长草(BFS)
    0.题目【问题描述】小明有一块空地,他将这块空地划分为n行m列的小块,每行和每列的长度都为1。小明选了其中的一些小块空地,种上了草,其他小块仍然保持是空地。这些草长得很快,每个月,草都会向外长出一些,如果一个小块种了草,则它将向自己的上、下、左、右四小块空地扩展,这四小块......
  • P8725 [蓝桥杯 2020 省 AB3] 画中漂流
    题目:链接:https://www.luogu.com.cn/problem/P8725思路:dp[i][j]表示第i个时刻还有多少体力之前的错误思路:dp[i][j][k]表示第i个时刻,在j位置,有k个体力。但是注意:这三个变量并不是相互独立!!动规的一个取变量原则应该是相互独立确定某个状态。剩下k体力和i时刻可以推出位置!!site......
  • 并查集
    介绍并查集主要用于处理一些不相交集合的合并问题,一些常见的用途有求联通子图,求最小生成树的Kruskal算法和求最近公共祖先等。并查集的基本操作主要有:初始化查询合并操作初始化假设有编号为1,2,3……,n的n个元素,我们用一个数组fa[]来储存每个元素的父节点。一开始,我们先将......
  • 蓝桥杯2016国赛-路径之谜
    0.题目小明冒充X星球的骑士,进入了一个奇怪的城堡。城堡里边什么都没有,只有方形石头铺成的地面。假设城堡地面是nxn个方格。【如图1.png】所示。按习俗,骑士要从西北角走到东南角。可以横向或纵向移动,但不能斜着走,也不能跳跃。每走到一个新方格,就要向正北方和正西方各射一......
  • 蓝桥杯训练
    P8712[蓝桥杯2020省B1]整数拼接-洛谷|计算机科学教育新生态(luogu.com.cn)题解:这道题和牛客类似,我们换一个思路我们可以开一个二维数组  一位用来记录拼在后面数的长度,一个用来记录这个数乘上10的(后面数的长度)模10我们直接乘1到10,全部记录下来然后枚举右边的数,看......
  • 太阳(蓝桥杯14届)
    https://www.lanqiao.cn/problems/3529/learning/?subject_code=2&group_code=5&match_num=14&match_flow=1&origin=cup1importjava.util.*;2//1:无需package3//2:类名必须Main,不可修改4importjava.util.Map.Entry;56publicclassDemo1{7......