首页 > 编程语言 >历届试题 合根植物 c++

历届试题 合根植物 c++

时间:2023-05-25 16:32:11浏览次数:44  
标签:Pre 小格子 合根 试题 temp int 植物 c++ key


问题描述


  w星球的一个种植园,被分成 m * n 个小格子(东西方向m行,南北方向n列)。每个格子里种了一株合根植物。
  这种植物有个特点,它的根可能会沿着南北或东西方向伸展,从而与另一个格子的植物合成为一体。


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


输入格式


  第一行,两个整数m,n,用空格分开,表示格子的行数、列数(1<m,n<1000)。
  接下来一行,一个整数k,表示下面还有k行数据(0<k<100000)
  接下来k行,第行两个整数a,b,表示编号为a的小格子和编号为b的小格子合根了。


  格子的编号一行一行,从上到下,从左到右编号。
  比如:5 * 4 的小格子,编号:
  1 2 3 4
  5 6 7 8
  9 10 11 12
  13 14 15 16
  17 18 19 20


样例输入


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


样例输出


5


样例说明


  其合根情况参考下图

历届试题 合根植物 c++_#include



注意:“6”那里也是一棵和根植物,题意为:多颗和根植物如果根连接在一起了便成了一颗和根植物,一颗和根植物仍然为和根植物,所以这个题是并查集问题。

#include <bits/stdc++.h>
using namespace std;
const int MAX = 0x3f3f3f;
int Pre[MAX];
bool t[MAX];
int m, n, k, all;
int Find(int key)
{
    int temp = key;
    while(temp != Pre[temp])
    {
        temp = Pre[temp];
    }
    int t;
    while(key != temp)
    {
        t = Pre[key];
        Pre[key] = temp;
        key = t;
    }
    return temp;
}
void Join(int a, int b)
{
    int x = Find(a);
    int y = Find(b);
    if(x != y)
        Pre[x] = y;
}
void Sove()
{
    memset(t, 0, sizeof(t));
    int num = 0;
    for(int i = 0; i < all; ++i)
        t[Find(i)] = 1;
    for(int i = 0; i < all; ++i)
        if(t[i])
         num++;
    cout << num << endl;
}
void Input()
{
    int a, b;
    scanf("%d %d", &m, &n);
    scanf("%d", &k);
    memset(Pre, 0, sizeof(Pre));
    all = m * n;
    for(int i = 0; i < all; ++i)
        Pre[i] = i;
    for(int i = 0; i < k; ++i)
    {
        scanf("%d %d", &a, &b);
        Join(a, b);
    }
}
int main()
{
    Input();
    Sove();
}



标签:Pre,小格子,合根,试题,temp,int,植物,c++,key
From: https://blog.51cto.com/u_16129621/6349659

相关文章

  • 恒生电子笔试(笔试流程,笔试介绍,题型,以往笔试题)
    2019网申渠道已开放,全国行程将在9月份正式开启完整流程:网申-笔试-2轮面试(群面+单面)-收到实习录取通知笔试流程:通过宣讲会,然后现场笔试。一般早上9点开始笔试,笔试时间两小时,大概1个多小时完成答题。笔试后一天或一周,收到人力通知参加面试笔试介绍:1.参加笔试的学生分A-F卷,每套卷子......
  • Selenium自动化测试面试必备:高频面试题及答案整理
    自动化测试已经成为现代软件测试中不可或缺的一部分。在自动化测试中,Selenium是最受欢迎的工具之一,因为它可以模拟用户与Web应用程序的交互。因此,对于许多测试工程师来说,熟练掌握Selenium框架是非常重要的。如果你正在寻找一份自动化测试工作,那么你可能会被问到一些关于Selenium的......
  • C++黑马程序员——P213-214. queue容器
    P213.queue容器——基本概念P214.queue容器——常用接口P213.queue容器基本概念 P214.queue常用接口示例1classPerson2{3public:4Person(stringname,intage){5this->m_Name=name;6this->m_Age=age;7......
  • C/C++图书信息管理系统[2023-05-25]
    C/C++图书信息管理系统[2023-05-25]图书信息管理系统主要内容:整个图书管理系统采用结构体作为基本数据结构,最终数据一定要保存到数据文件中。主函数通过switch语句来根据用户的需求跳转到各个模块,以实现用户的需要。系统要求能进行图书信息的浏览、添加、查询、修改、删除......
  • C++ MFC 学习笔记+小型通讯录系统实现
    [MFC最详细入门教程](https://blog.csdn.net/freeking101/article/details/101013627?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522168387812916782427455065%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=1683878129167824274550......
  • C++ 的使用
     C++语言在许多行业和领域都有广泛应用,包括:游戏开发:C++是游戏开发领域中最常用的编程语言之一,因为它具有高效的性能和直接控制硬件的能力。许多主要的游戏引擎,如UnrealEngine和Unity,都使用C++编写。嵌入式系统开发:C++可以在嵌入式系统中发挥重要作用,如智能手机、......
  • C++ 基本语法
     C++程序可以定义为对象的集合,这些对象通过调用彼此的方法进行交互。现在让我们简要地看一下什么是类、对象,方法、即时变量。对象- 对象具有状态和行为。例如:一只狗的状态-颜色、名称、品种,行为-摇动、叫唤、吃。对象是类的实例。类- 类可以定义为描述对象行为/状......
  • C/C++电话订餐信息处理系统[2023-05-25]
    C/C++电话订餐信息处理系统[2023-05-25]电话订餐信息处理系统要求提交:1个C源程序文件;1个word文档,包含源代码和运行过程截图;全部打包压缩成一个文件,文件名为“学号后2位+姓名+电话订餐信息处理系统”。1.题目要求一个小饭馆的生意非常红火,要想用餐必须提前一天打电话预......
  • C++ 简介
     C++是一种静态类型的、编译式的、通用的、大小写敏感的、不规则的编程语言,支持过程化编程、面向对象编程和泛型编程。C++被认为是一种中级语言,它综合了高级语言和低级语言的特点。C++是由BjarneStroustrup于1979年在新泽西州美利山贝尔实验室开始设计开发的。C++进......
  • 查看gcc/g++版本以及对应默认的的C++标准
    通过如下命令查看_cplusplus的值:g++-dM-E-xc++/dev/null|grep-F__cplusplus对应查表C++标准_cplusplusC++11201103LC++14201402LC++17201703L ......