蓝桥杯:合根植物

合根植物【并查集】

题目描述

w 星球的一个种植园,被分成 m×n 个小格子(东西方向 m 行,南北方向 n 列)。每个格子里种了一株合根植物。

类的加载

这种植物有个特点,它的根可能会沿着南北或东西方向伸展,从而与另一个格子的植物合成为一体。

license

如果我们告诉你哪些小格子间出现了连根现象,你能说出这个园中一共有多少株合根植物吗?

vue+elementui

输入描述

第一行,两个整数 m,n,用空格分开,表示格子的行数、列数(1≤m,n≤1000)。

双端队列

接下来一行,一个整数 k (0≤k≤105 ),表示下面还有 k 行数据。

nlp

接下来 k 行,每行两个整数 ab,表示编号为 a 的小格子和编号为 b 的小格子合根了。

DS18B20代码

格子的编号一行一行,从上到下,从左到右编号。

贪心算法

比如:5×4 的小格子,编号:

Anitmator

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20

输出描述

输出植物数量。

常用功能开发

输入输出样例

示例

输入

python ipidea

5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17

输出

logging

5

样例说明

Qt控件

其合根情况参考下图:

kettle

在这里插入图片描述

Windows 7 共享打印机

思路:

这题考的是最简单的并查集,并查集就是,一个集合里一开始只有一颗元素,就是本身,例如题目中的植物一样,一开始
自己一个就是一个集合,然后输入许多组有连根的植物,把所有连在一个根上的植物放到一个集合中,问一共有几个集合。还有
一个比喻讲就是,一帮强盗,输入许多组两个是一伙的强盗,问你一共有多少个团伙。这都是一类问题。

CCF-CSP考试

  • 并查集的实现分三步:
    1、初始化
    2、查找
    3、合并
    对于这个问题,我们先定义一个数组用于存放每个植物的主根,数组的下标是植物的编号,先将植物的主根定义为自己,就是
    第一步初始化。接下来输入许多组连根的植物,查找两个植物的主根,将两个植物的主根连在一起,那么和这两个主根相连的植物
    就在一个集合里了。不断对输入的两个植物进行连根。到最后遍历数组,如果一个植物的主根是本身,即f[i]==i,则这个植物就是
    主根,就算一个植物。

    精通Linux系列

  • 并查集最重要的就是:路径压缩,这样可以节省时间,如果不压缩,那么一个集合里植物之间的关系就成一个长链了
    变成一层一层的关系了,例如 1 -> 2 -> 3 -> 4 ,1植物的主根是2,2是3,3是4,对于 1 来说要找主根需要找三次,如果数据
    多了,会变得很慢,在 find 函数中 f[v]=find(f[v]) 就是路径压缩,在递归找主根时随便把集合里的每个植物的主根直接改成
    集合里的大主根,就是将1,2,3植物都改成 4 .大大节约了时间。

    jre

代码:

#include<stdio.h>
int f[1000001];
int n,m;

void init()
{   //初始化 
	for(int i=1;i<=n*m;i++)
		f[i]=i;  //每个植物还没连根 
	return ;
}

int find(int v)
{   //查找 
	if(f[v]==v) 
		return v;
	else 
	{
		f[v]=find(f[v]);
		return f[v];
	}
}

void merge(int v,int u)
{   //合并 
	int t1,t2;
	t1=find(v);  //找到一个植物的主根,也就是共同的祖先 
	t2=find(u);
	if(t1!=t2)  //如果两个植物的祖先不一样 
		f[t1]=f[t2];  //则将两个植物的祖先连在一起,也可以写成 f[t2]=f[t1],都一样 
	return ;
}

int main()
{
	int x,y,k,sum=0;
	scanf("%d %d",&n,&m);  //输入行数、列数 
	scanf("%d",&k); 
	init();   //将数组 f 初始化,开始每个植物只和自己连根 
	while(index--) 
	{
		scanf("%d %d",&x,&y);
		merge(x,y);  //合并连根植物 
	}
	for(int i=1;i<=n*m;i++)  //遍历每个植物 
		if(f[i]==i)   //如果一个植物连根还是自己,则算一个植物 
			sum++;   
	printf("%d",sum);
	return 0;
}

//合并连根植物
}
for(int i=1;i<=n*m;i++) //遍历每个植物
if(f[i]==i) //如果一个植物连根还是自己,则算一个植物
sum++;
printf(“%d”,sum);
return 0;
}

文件描述符


发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注