【数据结构 | C++】并查操作

news/2024/11/25 18:05:36/

现在有一个并查集,你需要完成合并和查询操作。

输入格式:
第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。
接下来 M 行,每行包含三个整数 zi,xi,yi 。
当 zi=1 时,将 xi与yi所在的集合合并。
当 zi=2 时,输出xi与yi 是否在同一集合内,是的输出 Y ;否则输出 N.

输出格式:
对于每一个zi=2的操作,都有一行输出,每行包含一个大写字母,为Y或者N 。

输入样例:
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
输出样例:
N
Y
N
Y

#include<iostream>
using namespace std;
const int N = 2e5 + 10;
int fa[N];
int n, m, p1, p2, p3;
int find(int k)
{if (fa[k] == k)return k;return fa[k] = find(fa[k]);
}
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++){fa[i] = i;}for (int i = 1; i <= m; i++){cin >> p1 >> p2 >> p3;if (p1 == 1){fa[find(p2)] = find(p3);}elseif (find(p2) == find(p3))printf("Y\n");elseprintf("N\n");}return 0;
}

http://www.ppmy.cn/news/1549872.html

相关文章

微信小程序技术架构图

一、视图层1.WXML&#xff08;WeiXin Markup Language&#xff09; 这是微信小程序的标记语言&#xff0c;类似于 HTML。它用于构建小程序的页面结构。例如&#xff0c;通过标签来定义各种视图元素&#xff0c;如<view>&#xff08;类似于 HTML 中的<div>&#xff…

python中lxml 库之 etree 使用详解

目录 一、 etree 介绍二、xpath 解析 html/xml1、第一步就是使用 etree 连接 html/xml 代码/文件。2、 xpath 表达式定位① xpath结合属性定位② xpath文本定位及获取③ xpath层级定位④ xpath索引定位⑤ xpath模糊匹配 一、 etree 介绍 lxml 库是 Python 中一个强大的 XML 处…

小程序-基于java+SpringBoot+Vue的流浪动物救助小程序设计与实现

项目运行 1.运行环境&#xff1a;最好是java jdk 1.8&#xff0c;我们在这个平台上运行的。其他版本理论上也可以。 2.IDE环境&#xff1a;IDEA&#xff0c;Eclipse,Myeclipse都可以。推荐IDEA; 3.tomcat环境&#xff1a;Tomcat 7.x,8.x,9.x版本均可 4.硬件环境&#xff1a…

LeetCode 4.寻找两个中序数组的中位数

力扣 4. 寻找两个正序数组的中位数 思路&#xff1a; 二分查找标记位计算中位数 细节&#xff1a; if (nums1.size() > nums2.size())return findMedianSortedArrays(nums2, nums1); 首先比较两个数组的大小&#xff0c;确保后续 nums1 的长度总是小于等于 nums2 的长度 …

如何控制自己玩手机的时间?两台苹果手机帮助自律

对一些人来说&#xff0c;被智能手机“绑架”是一件心甘情愿的事&#xff0c;和它相处的一天中&#xff0c;不必面对现实的压力&#xff0c;它就像个“舒适区”。这是因为在使用手机的过程中&#xff0c;应用程序&#xff08;尤其是游戏和社交媒体应用&#xff09;会不断刺激大…

企业OA管理系统:Spring Boot技术实现与案例研究

摘要 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步成熟。本文介绍了企业OA管理系统的开发全过程。通过分析企业OA管理系统管理的不足&#xff0c;创建了一个计算机管理企业OA管理系统的方案。文章介绍了企业OA管理系统的系统分析部…

深入浅出分布式缓存:原理与应用

文章目录 概述缓存分片算法1. Hash算法2. 一致性Hash算法3. 应用场景Redis集群方案1. Redis 集群方案原理2. Redis 集群方案的优势3. Java 代码示例:Redis 集群数据定位Redis 集群中的节点通信机制:Gossip 协议Redis 集群的节点通信:Gossip 协议Redis 集群的节点通信流程Red…

11.21作业

题目一&#xff1a; 题目&#xff1a; 函数fun功能&#xff1a;求出二维数组周边元素之和&#xff0c;作为函数值返回。 二维数组的值已经在主函数中赋予。 代码&#xff1a; #include <stdio.h> #define M 4 #define N 5///$ /// 函数fun功能&#xff1a;求出二维数…