当前位置：首页 > news >正文

cf div3 998 E(并查集）

news 来源：原创 2025/5/15 16:23:25

E :
给出两个简单无向图（没有重边和自环）f g .
可以对f 进行删边和加边的操作。问至少操作多少次，使得 f 和 g 的点的联通情况相同（并查集的情况相同）

首先思考删边：
对于我 f 图存在边 e ，只要这个边所连接的两个点在g 中是不联通的，那么这条边一定要删除。

现在的问题是，所有要删的边都删除了吗》答案是 Yes.
对于两个点 a b ，如果他们之间联通但不是直接通过直接的一条边。那么我path 中的边，一定在我遍历e 的时候，删掉了。

所以到现在为止删边的操作已经完成了。
现在考虑加边的操作：
加边的数量可以通过连通块的数量的差值直接计算。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
struct DSU {vector<int> p, siz;DSU(int n) : p(n + 1), siz(n + 1, 1) {iota(p.begin(), p.end(), 0);// 会将容器 p 中的元素依次赋值为 0, 1, 2, 3, ...，直到填满整个范围。}int find(int x) {while (x != p[x]) x = p[x] = p[p[x]]; // 路径压缩return x;}bool same(int x, int y) {return find(x) == find(y);}bool uno(int x, int y) {x = find(x), y = find(y);if (same(x, y)) return false;siz[x] += siz[y];p[y] = x;return true;}int size(int x) {return siz[find(x)];}
};
void solve()
{int n,m1,m2;cin>>n>>m1>>m2;int u,v;vector<PII>e1(m1);for (int i=0;i<m1;i++){cin>>e1[i].first>>e1[i].second;}DSU dsu1(n),dsu2(n);for (int i=0;i<m2;i++){cin>>u>>v;dsu2.uno(u,v);}int res=0;for (auto [u,v]:e1){if (!dsu2.same(u,v)){res++;}else dsu1.uno(u,v);}int siz1=0,siz2=0;for (int i=1;i<=n;i++){siz1+= dsu1.find(i)==i;siz2+= dsu2.find(i)==i;}res+=siz1-siz2;cout<<res<<"\n";
}
int main()
{std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;cin>>t;while (t--){solve();}return 0;
}

cf div3 998 E(并查集）

E : 给出两个简单无向图 （没有重边和自环）f g . 可以对f 进行删边和加边的操作。问至少操作多少次 ，使得 f 和 g 的点的联通情况相同（并查集的情况相同） 首先思考删边 ： 对于我 f 图存在边 e &#x…...

编程日记 2025/5/15 16:23:25

【C++】string类(上)：string类的常用接口介绍

文章目录前言一、C中设计string类的意义二、string类的常用接口说明1. string类对象的常见构造2. string类对象的容量操作2.1 size、capacity 和 empty的使用2.2 clear的使用2.3 reserve的使用2.4 resize的使用 3. string类对象的访问及遍历操作3.1 下标[ ] 和 at3.2 迭代器it…...

编程日记 2025/5/15 16:23:24

[SAP ABAP] ABAP SQL跟踪工具

事务码ST05 操作步骤步骤1：使用事务码ST05之前，将要检测的程序生成的页面先呈现出来，这里我们想看下面程序的取数操作，所以停留在选择界面步骤2： 新建一个GUI窗口，输入事务码ST05，点击 Acti…...

编程日记 2025/5/15 16:23:23

OpenGL学习笔记（六）：Transformations 变换（变换矩阵、坐标系统、GLM库应用）

文章目录向量变换使用GLM变换（缩放、旋转、位移）将变换矩阵传递给着色器坐标系统与MVP矩阵三维变换绘制3D立方体 & 深度测试（Z-buffer）练习1——更多立方体现在我们已经知道了如何创建一个物体、着色、加入纹理。但它们都还…...

编程日记 2025/5/15 16:23:23

PHP 常用函数2025.02

PHP implode() 函数语法 implode(separator,array) 参数描述separator可选。规定数组元素之间放置的内容。默认是 ""（空字符串）。array必需。要组合为字符串的数组。技术细节返回值：返回一个由数组元素组合成的字符串。PHP 版…...

编程日记 2025/5/15 16:23:21

1. 【.NET 8 实战--孢子记账--从单体到微服务--转向微服务】--前言

在我们的专栏《单体开发》中，我们实现了一个简单的记账软件的服务端，并且成功上线。随着用户数量的不断增长，问题逐渐开始显现。访问量逐渐增加，服务端的压力也随之加大。随着访问量的攀升，服务端的响应时间变得越来越…...

编程日记 2025/5/15 23:55:09

02.04 数据类型

请写出以下几个数据的类型： 整数 a ----->int a的地址 ----->int* 存放a的数组b ----->int[] 存放a的地址的数组c ----->int*[] b的地址 ----->int* c的地址 ----->int** 指向printf函数的指针d ----->int (*)(const char*, ...) …...

编程日记 2025/5/11 18:20:02

WPS动画：使图形平移、围绕某个顶点旋转一定角度

1、平移案例三角形如下图，需求：该三角形的A点平移至原点 （1）在预想动画结束的位置绘制出图形 （2）点击选中原始图像，插入/动画/绘制自定义路径/直线 （3）十字星绘制的直线…...

编程日记 2025/5/13 9:24:16

想表示消息返回值为Customer集合

道奈特(240***10) 14:34:55 EA中序列图。我想表示消息返回值为 Customer 集合。目前只有一个Customer实体类，我需要另外新建一个CustomerList 类吗？ 潘加宇(35***47) 17:01:26 不需要。如果是分析，在类的操作中，定义一个参数&…...

编程日记 2025/5/15 16:23:19

93，【1】buuctf web [网鼎杯 2020 朱雀组]phpweb

进入靶场页面一直在刷新在 PHP 中，date() 函数是一个非常常用的处理日期和时间的函数，所以应该用到了再看看警告的那句话 Warning: date(): It is not safe to rely on the systems timezone settings. You are *required* to use the date.timez…...

编程日记 2025/5/15 16:23:18

五、定时器实现呼吸灯

5.1 定时器与计数器简介定时器是一种通过对内部时钟脉冲计数来测量时间间隔的模块。它的核心是一个递增或递减的寄存器（计数器值）。如果系统时钟为 1 MHz，定时器每 1 μs 计数一次。计数器是一种对外部事件（如脉冲信号&#xff…...

编程日记 2025/5/15 16:23:17

顺序打印数字的进一步理解

之前博客写了篇博文，面试时要求使用多线程顺序打印ABC循环20次，这是我当时使用join函数实现代码： public class TestABCJoin {public static void main(String[] args) {// 创建任务Runnable taskA () -> {for (int i 0; i < 5; i) …...

编程日记 2025/5/13 23:52:58

使用React和Material-UI构建TODO应用的前端UI

使用React和Material-UI构建TODO应用的前端UI 引言环境准备代码解析1. 导入必要的模块2. 创建React组件3. 定义函数3.1 获取TODO列表3.2 创建TODO项3.3 更新TODO项3.4 删除TODO项3.5 处理编辑点击事件3.6 关闭编辑对话框3.7 保存编辑内容 4. 使用Effect钩子5. 渲染组件功能实现…...

编程日记 2025/5/12 14:41:17

开屏广告-跳过神器

给大家介绍一款超实用的软件——SKIP，它堪称李跳跳的最佳平替！这款软件已经在Github开源免费，完全无需担心内置源问题，也无需导入任何规则。安装完成后，即可直接使用，非常便捷！ 首次打开软件时…...

编程日记 2025/5/12 3:18:32

bat脚本实现自动化漏洞挖掘

bat脚本 BAT脚本是一种批处理文件，可以在Windows操作系统中自动执行一系列命令。它们可以简化许多日常任务，如文件操作、系统配置等。 bat脚本执行命令 echo off#下面写要执行的命令 httpx 自动存活探测 echo off httpx.exe -l url.txt -o 0.txt nuc…...

编程日记 2025/5/14 8:15:13

如何运行Composer安装PHP包安装JWT库

1. 使用Composer Composer是PHP的依赖管理工具，它允许你轻松地安装和管理PHP包。对于JWT，你可以使用firebase/php-jwt这个库，这是由Firebase提供的官方库。安装Composer（如果你还没有安装的话）： 访问Co…...

编程日记 2025/5/15 7:24:15

(回溯递归dfs 电话号码的字母组合 remake)leetcode 17

只找边界条件和非边界条件，剩下的交给数学归纳法就行，考虑子问题的重复性 [class Solution {vector<string>str { "","","abc","def","ghi","jkl","mno","pqrs"…...

编程日记 2025/5/15 8:32:20

it基础使用--5---git远程仓库

文章目录 it基础使用--5---git远程仓库1. 按顺序看2. 什么是远程仓库3. Gitee操作3.1 新建远程仓库3.2 远程操作基础命令3.3 查看当前所有远程地址别名 git remote -v3.4 创建远程仓库别名 git remote add 别名远程地址3.4 推送本地分支到远程仓库 git push 别名分支3.5 拉取…...

编程日记 2025/5/15 0:36:56

Git 的起源与发展

序章：版本控制的前世今生在软件开发的漫长旅程中，版本控制犹如一位忠诚的伙伴，始终陪伴着开发者们。它的存在，解决了软件开发过程中代码管理的诸多难题，让团队协作更加高效，代码的演进更加有序。简单来…...

编程日记 2025/5/14 4:37:33

c++提取矩形区域图像的梯度并拟合直线

c提取旋转矩形区域的边缘最强梯度点，并拟合直线 #include <opencv2/opencv.hpp> #include <iostream> #include <vector>using namespace cv; using namespace std;int main() {// 加载图像Mat img imread("image.jpg", IMREAD_GRAYS…...

编程日记 2025/5/11 3:48:15

【PyQt】超级超级笨的pyqt计算器案例

计算器 1.QT Designer设计外观 1.pushButton2.textEdit3.groupBox4.布局设计 2.加载ui文件导入模块： sys：用于处理命令行参数。 QApplication：PyQt5 应用程序类。 QWidget：窗口基类。 uic：用于加载 .ui 文件。…...

编程日记 2025/5/15 9:03:23

每日一题——小根堆实现堆排序算法

小根堆实现堆排序算法堆排序的基本思想堆排序的步骤实现步骤1. 构建小根堆2. 删除最小元素并调整堆 C语言实现输出示例代码解释1. percolateDown 函数2. buildMinHeap 函数3. heapSort 函数4. printArray函数排序过程详解步骤1：构建小根堆步骤2：删除堆…...

编程日记 2025/5/14 22:49:08

k8s集群

文章目录项目描述项目环境系统与软件版本概览项目步骤环境准备IP地址规划关闭selinux和firewall配置静态ip地址修改主机名添加hosts解析项目步骤一、使用kubeadm安装k8s单master的集群环境（1个master2个node节点）1、互相之间建立免密通道2.关闭交换分…...

编程日记 2025/5/14 11:02:22

数据分析系列--[11] RapidMiner,K-Means聚类分析(含数据集)

一、数据集二、导入数据三、K-Means聚类数据说明:提供一组数据,含体重、胆固醇、性别。分析目标:找到这组数据中需要治疗的群体供后续使用。一、数据集点击下载数据集二、导入数据三、K-Means聚类 Ending, congratulations, youre done....

编程日记 2025/5/12 10:26:25

技术架构师成长路线（2025版）

目录通用知识计算机原理（1 - 2 个月） 数据结构（2 - 3 个月） 网络编程（1 - 2 个月） 软件工程（1 个月） 基础知识 Java 编程语言基础（2 - 3 个月） JVM&…...

编程日记 2025/5/7 9:07:26

NetLify账号无法登录解决办法

本文收录在【建站】专栏内，专栏目录：【建站】专栏目录用github账号登录时，说校验失败 Authentication Error Authenticating failed due to the following error: Your account requires additional verification. Please check your email…...

编程日记 2025/5/14 6:59:56

linux本地部署deepseek-R1模型

国产开源大模型追平甚至超越了CloseAI的o1模型，大国崛起时刻！！！ DeepSeek R1 本地部署指南在人工智能技术飞速发展的今天，本地部署AI模型成为越来越多开发者和企业关注的焦点。本文将详细介绍如何在本地部署DeepS…...

编程日记 2025/5/12 8:49:35

集合通讯概览

集合通信概览 （1）通信的算法是根据通讯的链路组成的 （2）因为通信链路跟硬件强相关，所以每个CCL的库都不一样芯片与芯片、不同U之间是怎么通信的多卡训练：多维并行（xxx并行在上一期已经讲述…...

编程日记 2025/5/15 11:02:27

如何解决云台重力补偿？

如何解决云台重力补偿？最近在调试步兵云台的时候，由于枪管、图传、摄像头等重力的原因，pitch轴的参数尤其难以调整，又不想抬升和降低使用两套不同的参数，所以使用了重力补偿，效果也是比较理想的，于是整理为一篇文章记录一下一、问题根源：枪管重力在“搞事情” 想象…...

编程日记 2025/5/15 1:01:55

【LeetCode 刷题】回溯算法(4)-排列问题

此博客为《代码随想录》二叉树章节的学习笔记，主要内容为回溯算法排列问题相关的题目解析。文章目录 46.全排列47.全排列 II 46.全排列题目链接 class Solution:def permute(self, nums: List[int]) -> List[List[int]]:res, path [], []used [0] * len(n…...

编程日记 2025/5/14 23:50:38

FPGA|IP核PLL调用测试：建立工程

闲来无事，测试下FPGA的IP核调用一、生成工程 1、打开软件新建工程 2、命名为PLL_test 3、选择芯片型号 4、生成工程如图...

编程日记 2025/4/27 14:03:23

数据的表示和运算

一-定点数的表示 1-定点数和浮点数定点数：小数点的位置固定（常规计数） 浮点数：小数点的位置不固定（科学计数法） 2-定点数的表示 ①无符号数整个机器字长的全部二进制位均为数值位，没有符号…...

编程日记 2025/5/13 1:51:27

22.Word：小张-经费联审核结算单❗【16】

目录 NO1.2 NO3.4 NO5.6.7 NO8邮件合并 MS搜狗输入法 NO1.2 用ms打开文件，而不是wps❗不然后面都没分布局→页面设置→页面大小→页面方向→上下左右：页边距→页码范围：多页：拼页光标处于→布局→分隔符：分节符…...

编程日记 2025/5/14 3:30:48

鲸鱼算法 matlab pso

算法原理鲸鱼优化算法的核心思想是通过模拟座头鲸的捕食过程来进行搜索和优化。座头鲸在捕猎时会围绕猎物游动并产生气泡网，迫使猎物聚集。这一行为被用来设计搜索策略，使算法能够有效地找到全局最优解。算法步骤 ‌初始化‌：随机生成一…...

编程日记 2025/5/9 18:06:37

c++之模板进阶

在前面的文章中，我们已经简单的了解了模板的使用，在这篇文章中，我们将继续深入探讨模板 1.模板的特化 1.1 概念通常情况下，使用模板可以实现一些与类型无关的代码，但对于一些特殊类型的可能会得到一些错误的结果&a…...

编程日记 2025/5/13 2:25:51

C语言中的信号量

信号是操作系统中用来传递特定消息的机制。操作系统可以使用这种方式将程序运行过程中发生的各类特殊情况发送给程序，并按照其指定的逻辑进行处理。信号名称都以 “SIG” 作为前缀，如程序访问非法内存时，会产生名为 SIGSEGV 的信号。程序需…...

编程日记 2025/5/15 5:27:57

AI主流大模型介绍和API价格比较

主流的大模型系列 ###1. OpenAI: GPT-4，GPT-4 Turbo， GPT-4o OpenAI 的介绍： 全称：Open Artificial Intelligence，简称OpenAI。性质：起初为非营利性组织，后转变为由营利性公司OpenAI LP及非营…...

编程日记 2025/5/14 17:13:33

自主Shell命令行解释器

什么是命令行我们一直使用的"ls","cd","pwd","mkdir"等命令，都是在命令行上输入的，我们之前对于命令行的理解： 命令行是干啥的？是为我们做命令行解释的。命令行这个东西实际上是我们…...

编程日记 2025/5/12 15:16:24

git笔记-简单入门

git笔记 git是一个分布式版本控制系统，它的优点有哪些呢？分为以下几个部分与集中式的版本控制系统比起来，不用担心单点故障问题，只需要互相同步一下进度即可。支持离线编辑，每一个人都有一个完整的版本库。跨平台支持…...

编程日记 2025/5/15 2:00:32

重新刷题求职2-DAY1

DAY1 1.704. 二分查找给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。最普通的二分查找，查用的习惯左闭右…...

编程日记 2025/5/15 16:01:15

浅析DDOS攻击及防御策略

DDoS（分布式拒绝服务）攻击是一种通过大量计算机或网络僵尸主机对目标服务器发起大量无效或高流量请求，耗尽其资源，从而导致服务中断的网络攻击方式。这种攻击方式利用了分布式系统的特性，使攻击规模更大、影响范围更广…...

编程日记 2025/5/14 21:39:24

路径规划之启发式算法之二十九：鸽群算法（Pigeon-inspired Optimization, PIO）

鸽群算法（Pigeon-inspired Optimization, PIO）是一种基于自然界中鸽子群体行为的智能优化算法，由Duan等人于2014年提出。该算法模拟了鸽子在飞行过程中利用地标、太阳和磁场等导航机制的行为，具有简单、高效和易于实现的特点，适用于解决连续优化问题。更多的仿生群体算法…...

编程日记 2025/5/13 5:38:16

SwiftUI 在 Xcode 预览修改视图 FetchedResults 对象的属性时为什么会崩溃？

概览从 SwiftUI 诞生那天起，让秃头码农们又爱又恨的 Xcode 预览就在界面调试中扮演了及其重要的角色。不过，就是这位撸码中的绝对主角却尝尝在关键时刻“掉链子”。比如当修改 SwiftUI 视图中 FetchedResults 对象的属性时，Xcode 预览可能…...

编程日记 2025/5/12 12:54:12

pytorch实现基于Word2Vec的词嵌入

PyTorch 实现 Word2Vec（Skip-gram 模型） 的完整代码，使用中文语料进行训练，包括数据预处理、模型定义、训练和测试。 1. 主要特点支持中文数据，基于 jieba 进行分词使用 Skip-gram 进行训练，适用于小数…...

编程日记 2025/5/9 11:31:27

MVC 文件夹：架构之美与实际应用

MVC 文件夹：架构之美与实际应用引言 MVC（Model-View-Controller）是一种设计模式，它将应用程序分为三个核心组件：模型（Model）、视图（View）和控制器（Controller）。这种架构模式不仅提高了代码的可维护性和可扩展性，而且使得开发流程更加清晰。本文将深入探讨MVC文…...

编程日记 2025/5/15 13:48:17

from flask import Flask, render_template, request, jsonify import sys from io import StringIO import contextlib import subprocess import importlib import threading import time import ast import reapp Flask(__name__)RESTRICTED_PACKAGES {tkinter: 抱歉&…...

编程日记 2025/5/15 8:50:47

The Simulation技术浅析（四）：随机数生成

随机数生成技术是 The Simulation 中的核心组成部分，广泛应用于蒙特卡洛模拟、密码学、统计建模等领域。随机数生成技术主要分为伪随机数生成器（PRNG，Pseudo-Random Number Generator）和真随机数生成器（TRNG，True Random Number Generator）。 1. 伪随机数生成器（PR…...

编程日记 2025/5/12 16:03:45

centos stream 9 安装 libstdc++-static静态库

yum仓库中相应的镜像源没有打开，libstdc-static在CRB这个仓库下，但是查看/etc/yum.repos.d/centos.repo，发现CRB镜像没有开启。解决办法如下图开启CRB镜像， 然后执行 yum makecache yum install glibc-static libstdc-static…...

编程日记 2025/5/14 9:27:03

相关文章：