[蓝桥杯 2017 国 C] 合根植物

[蓝桥杯 2017 国 C] 合根植物

题目描述

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

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

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

输入格式

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

接下来一行,一个整数 k k k,表示下面还有 k k k 行数据 ( 0 < k < 1 0 5 ) (0<k<10^5) (0<k<105)

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

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

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

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

输出格式

一行一个整数,表示答案

样例 #1

样例输入 #1

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

样例输出 #1

5

提示

样例解释

时限 1 秒, 256M。蓝桥杯 2017 年第八届国赛

考查知识点:并查集
本题解题关键:

找到多少珠合根植物=找到根的数目 也就是: fa[i]==i

初始化:

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

查找:

int find(int i)
{
	
	if(i==fa[i])
	return i;
	else

		return fa[i]=find(fa[i]);
	
	
}

合并:

void  unio(int x,int y)
{
	
	int x_1=find(x);
	int y_1=find(y);
	if(x_1!=y_1)
	fa[x_1]=y_1;
}

在这定义函数不能用union:它是关键字

完整代码:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000001;
int fa[N];

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

		return fa[i]=find(fa[i]);
	
	
}

void  unio(int x,int y)
{
	
	int x_1=find(x);
	int y_1=find(y);
	if(x_1!=y_1)
	fa[x_1]=y_1;
}
signed main()
{
	int m,n;
	cin>>m>>n;
	int w=m*n;
	init(w);
	int k;
	cin>>k;
	int o,p;
	int ans=0;
	for(int i=1;i<=k;i++)
	{
		cin>>o>>p;
		unio(o,p);
	}
	for(int i=1;i<=w;i++)
	{
	   if(fa[i]==i)
	   ans++;
	}
	cout<<ans;
	return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/520188.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【MySQL】增删改查操作(基础)

文章目录 1、新增操作&#xff08;Create&#xff09;1.1单行数据全列插入1.2多行数据指定列插入 2、查询操作&#xff08;Retrieve&#xff09;2.1全列查询2.2指定列查询2.3指定列查询2.4别名&#xff08;as&#xff09;2.5去重&#xff08;distinct&#xff09;2.6排序&#…

数据结构—图

图的基本概念 图就是由顶点的有穷非空集合和顶点之间的边组成的集合。通常表示为&#xff1a;G(V,E)&#xff0c;其中&#xff0c;G 表示一个图&#xff0c;V 表示顶点的集合&#xff0c;E 表示边的集合。 顶点 图中的数据元素&#xff0c;我们称之为顶点&#xff0c;图至少有…

常见现代卷积神经网络(Pytorch 09)

本章将介绍现代的 卷积神经网络架构&#xff0c;许多现代卷积神经网络的研究都是建立在这一章的基础上的。在本章中的每一个模型都曾一度占据主导地位&#xff0c;其中许多模型都是 ImageNet竞赛 的优胜者。ImageNet竞赛自2010年以来&#xff0c;一直是计算机视觉中监督学习进展…

面试题——JVM老年代空间担保机制(我的想法)

这里借用一下人家的图&#xff0c;来说一下我的想法&#xff0c;嘻嘻。。。。 原文链接&#xff1a;一道面试题&#xff1a;JVM老年代空间担保机制-CSDN博客? 嗯&#xff0c;我觉得老年代担保机制的主要作用就是避免频繁触发FULL GC&#xff0c;这其实也是因为年轻代Minor GC…

Java项目:基于Springboot+vue社区医院管理系统设计与实现(源码+数据库+毕业论文)

一、项目简介 本项目是一套基于Springbootvue社区医院管理系统 包含&#xff1a;项目源码、数据库脚本等&#xff0c;该项目附带全部源码可作为毕设使用。 项目都经过严格调试&#xff0c;eclipse或者idea 确保可以运行&#xff01; 该系统功能完善、界面美观、操作简单、功能…

数据结构之顺序表的相关知识点及应用

个人主页&#xff08;找往期文章包括但不限于本期文章中不懂的知识点&#xff09;&#xff1a;我要学编程(ಥ_ಥ)-CSDN博客 目录 顺序表的概念及结构 顺序表的分类 顺序表的实现 在顺序表中增加数据 在顺序表中删除数据 在顺序表中查找数据 顺序表源码 顺序表的概念…

浮动辊位移测量功能块(CODESYS ST代码)

1、张力测量+标定(ST代码) 张力测量+标定(ST代码)_动态舞轮控制张力-CSDN博客文章浏览阅读804次。跳舞轮对应张力调节范围,我们可以通过改变气缸的气压方式间接改变,张力跳舞轮在收放卷闭环控制上的详细应用,可以参看下面的文章链接,这里我们主要讨论精密可调气阀的模拟量…

Java | Leetcode Java题解之第6题Z字形变换

题目&#xff1a; 题解&#xff1a; class Solution {public String convert(String s, int numRows) {int n s.length(), r numRows;if (r 1 || r > n) {return s;}int t r * 2 - 2;int c (n t - 1) / t * (r - 1);char[][] mat new char[r][c];for (int i 0, x …

[Spring Cloud] gateway全局异常捕捉统一返回值

文章目录 处理转发失败的情况全局参数同一返回格式操作消息对象AjaxResult返回值状态描述对象AjaxStatus返回值枚举接口层StatusCode 全局异常处理器自定义通用异常定一个自定义异常覆盖默认的异常处理自定义异常处理工具 在上一篇章时我们有了一个简单的gateway网关 [Spring C…

比selenium体验更好的ui自动化测试工具: cypress介绍

话说 Cypress is a next generation front end testing tool built for the modern web. And Cypress can test anything that runs in a browser.Cypress consists of a free, open source, locally installed Test Runner and a Dashboard Service for recording your tests.…

leetcode077——排序链表

题目&#xff1a; 给定链表的头结点 head &#xff0c;请将其按 升序 排列并返回 排序后的链表 。 示例 1&#xff1a; 输入&#xff1a;head [4,2,1,3] 输出&#xff1a;[1,2,3,4] 思路&#xff1a; 1.找链表中点【使用快慢指针 慢指针每次移动一步&#xff0c;快指针每…

基于单片机12864的出租车计价器设计

**单片机设计介绍&#xff0c;基于单片机12864的出租车计价器设计 文章目录 一 概要二、功能设计三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机和12864液晶显示屏的出租车计价器设计&#xff0c;主要是利用单片机的强大控制能力和液晶显示屏的直观显示特性&…

牛客网BC-125 序列中整数去重复(难题讲解)

题目如下 --------------------------------------------------------------------------------------------------------------------------------- 题目讲解&#xff08;思路&#xff09; -------------------------------------------------------------------------------…

单一职责原则

1.1 阅读干吗不直接用手机&#xff1f; 电子阅读器比较专注&#xff0c;而手机功能比较多&#xff0c;影响专注。 1.2 手机不纯粹 手机确实很方便。但是现在的手机就是一台小型智能电脑。它不仅能打电话&#xff0c;还能听音乐、看电影电视、与个人交流、与一群人群聊&#…

基于java+SpringBoot+Vue的大学生入学审核系统设计与实现

基于javaSpringBootVue的大学生入学审核系统设计与实现 开发语言: Java 数据库: MySQL技术: SpringBoot VUE工具: IDEA/Eclipse、Navicat、Maven 系统展示 前台展示 入学办理模块&#xff1a;学生可以提交入学申请并跟踪入学办理进度。 后台展示 学生管理模块&#xff1…

【Docker系列】在 Linux 上安装 Docker Compose 的简明步骤

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

前端学习之DOM编程案例:抽奖案例

代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>抽奖案例</title><style>*{margin: 0;padding: 0;}</style> </head> <body><div id"container"&g…

【放假第3天】幻兽帕鲁 雾锁王国 我的世界 游戏云服务器选购指南 附最新价格对比表 新手、小白秒懂

更新日期&#xff1a;4月6日&#xff08;半年档 价格回调&#xff0c;京东云采购季持续进行&#xff09; 本文纯原创&#xff0c;侵权必究 【云服务器推荐】价格对比&#xff01;阿里云 京东云 腾讯云 选购指南视频截图 《最新对比表》已更新在文章头部—腾讯云文档&#xf…

LeetCode 1483.树节点的第 K 个祖先:树上倍增

【LetMeFly】1483.树节点的第 K 个祖先&#xff1a;树上倍增 力扣题目链接&#xff1a;https://leetcode.cn/problems/kth-ancestor-of-a-tree-node/ 给你一棵树&#xff0c;树上有 n 个节点&#xff0c;按从 0 到 n-1 编号。树以父节点数组的形式给出&#xff0c;其中 paren…

redis主从复制与哨兵模式

redis主从复制 Redis主从复制&#xff08;Redis replication&#xff09;是Redis提供的一种数据备份和故障转移机制。通过主从复制&#xff0c;可以将一个Redis服务器&#xff08;主节点&#xff09;的数据复制到一个或多个Redis服务器&#xff08;从节点&#xff09;。这样做…