代码随想录算法训练营第六十一天 | 108. 冗余连接 109. 冗余连接II
108. 冗余连接
题目链接:KamaCoder
文档讲解:代码随想录
状态:AC
Java代码:
import java.util.*;class Main {public static int[] father;public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();father = new int[n + 1];init();String result = "";for (int i = 0; i < n; i++) {int s = scan.nextInt();int t = scan.nextInt();if (isSame(s, t)) {result = s + " " + t;} else {join(s, t);}}scan.close();System.out.println(result);}// 并查集初始化public static void init() {for (int i = 0; i < father.length; i++) {father[i] = i; // 每个节点的父节点初始化为自己}}// 并查集查找 (带路径压缩)public static int find(int u) {if (u == father[u]) {return u;}return (father[u] = find(father[u]));}// 判断两个节点是否在同一集合public static boolean isSame(int u, int v) {return find(u) == find(v);}// 合并两个集合public static void join(int u, int v) {u = find(u);v = find(v);if (u != v) {father[v] = u; // 将 v 的根节点指向 u}}
}
109. 冗余连接II
题目链接:KamaCoder
文档讲解:代码随想录
状态:没做出来
Java代码:
import java.util.*;public class Main {/*** 并查集模板*/static class Disjoint {private final int[] father;public Disjoint(int n) {father = new int[n];for (int i = 0; i < n; i++) {father[i] = i;}}public void join(int n, int m) {n = find(n);m = find(m);if (n == m) return;father[n] = m;}public int find(int n) {return father[n] == n ? n : (father[n] = find(father[n]));}public boolean isSame(int n, int m) {return find(n) == find(m);}}static class Edge {int s;int t;public Edge(int s, int t) {this.s = s;this.t = t;}}static class Node {int id;int in;int out;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();List<Edge> edges = new ArrayList<>();Node[] nodeMap = new Node[n + 1];for (int i = 1; i <= n; i++) {nodeMap[i] = new Node();}Integer doubleIn = null;for (int i = 0; i < n; i++) {int s = scanner.nextInt();int t = scanner.nextInt();//记录入度nodeMap[t].in++;if (!(nodeMap[t].in < 2)) doubleIn = t;Edge edge = new Edge(s, t);edges.add(edge);}Edge result = null;//存在入度为2的节点,既要消除入度为2的问题同时解除可能存在的环if (doubleIn != null) {List<Edge> doubleInEdges = new ArrayList<>();for (Edge edge : edges) {if (edge.t == doubleIn) doubleInEdges.add(edge);if (doubleInEdges.size() == 2) break;}Edge edge = doubleInEdges.get(1);if (isTreeWithExclude(edges, edge, nodeMap)) {result = edge;} else {result = doubleInEdges.get(0);}} else {//不存在入度为2的节点,则只需要解除环即可result = getRemoveEdge(edges, nodeMap);}System.out.println(result.s + " " + result.t);}public static boolean isTreeWithExclude(List<Edge> edges, Edge exculdEdge, Node[] nodeMap) {Disjoint disjoint = new Disjoint(nodeMap.length + 1);for (Edge edge : edges) {if (edge == exculdEdge) continue;//成环则不是树if (disjoint.isSame(edge.s, edge.t)) {return false;}disjoint.join(edge.s, edge.t);}return true;}public static Edge getRemoveEdge(List<Edge> edges, Node[] nodeMap) {int length = nodeMap.length;Disjoint disjoint = new Disjoint(length);for (Edge edge : edges) {if (disjoint.isSame(edge.s, edge.t)) return edge;disjoint.join(edge.s, edge.t);}return null;}}
相关文章:
代码随想录算法训练营第六十一天 | 108. 冗余连接 109. 冗余连接II
108. 冗余连接 题目链接:KamaCoder 文档讲解:代码随想录 状态:AC Java代码: import java.util.*;class Main {public static int[] father;public static void main(String[] args) {Scanner scan new Scanner(System.in);int n…...
RoboVQA:机器人多模态长范围推理
23 年 11 月来自 Google Deepmind 的论文“RoboVQA: Multimodal Long-Horizon Reasoning for Robotics”。 本文提出一种可扩展、自下而上且本质多样化的数据收集方案,该方案可用于长期和中期的高级推理,与传统的狭窄自上而下的逐步收集相比,…...
TCP/IP原理详细解析
前言 TCP/IP是一种面向连接,可靠的传输,传输数据大小无限制的。通常情况下,系统与系统之间的http连接需要三次握手和四次挥手,这个执行过程会产生等待时间。这方面在日常开发时需要注意一下。 TCP/IP 是互联网的核心协议族&…...
Microsof Visual Studio Code 安装教程(中文设置)
VS Code 是一个免费的代码编辑器,可在 macOS、Linux 和 Windows作系统上运行。启动和运行 VS Code 既快速又简单。VS Code(全称 Visual Studio Code)是一款由Microsoft 推出的免费、开源、跨平台的代码编辑器,拥有强大的功能和灵活…...
python爬虫:Android自动化工具Auto.js的详细使用
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 1. Auto.js 简介2. 安装与配置2.1 安装 Auto.js2.2 安装 Python 环境2.3 安装 ADB 工具3. Python 与 Auto.js 结合3.1 通过 ADB 执行 Auto.js 脚本3.2 通过 Python 控制 Auto.js3.3 通过 Python 与 Auto.js 交互4. 常用…...
Unity DOTS从入门到精通之 自定义Authoring类
文章目录 前言安装 DOTS 包什么是Authoring1. 实体组件2. Authoring类 前言 DOTS(面向数据的技术堆栈)是一套由 Unity 提供支持的技术,用于提供高性能游戏开发解决方案,特别适合需要处理大量数据的游戏,例如大型开放世…...
linux 软件安装(上)
一、基础环境准备 1.1、安装VM 1.2、在VM上导入linux iso镜像,装好linux系统 华为centos镜像下载地址 https://mirrors.huaweicloud.com/centos/ https://mirrors.huaweicloud.com/centos/7.9.2009/isos/x86_64/ 网易centos镜像下载地址 htt…...
php虚拟站点提示No input file specified时的问题及权限处理方法
访问站点,提示如下 No input file specified. 可能是文件权限有问题,也可能是“.user.ini”文件路径没有配置对,最简单的办法就是直接将它删除掉,还有就是将它设置正确 #配置成自己服务器上正确的路径 open_basedir/mnt/qiy/te…...
【江协科技STM32】ADC数模转换器-学习笔记
ADC简介 ADC(Analog-Digital Converter)模拟-数字转换器ADC可以将引脚上连续变化的模拟电压转换为内存中存储的数字变量,建立模拟电路到数字电路的桥梁,ADC是一种将连续的模拟信号转换为离散的数字信号的设备或模块12位逐次逼近型…...
QT系列教程(20) Qt 项目视图便捷类
视频连接 https://www.bilibili.com/video/BV1XY41127t3/?vd_source8be9e83424c2ed2c9b2a3ed1d01385e9 Qt项目视图便捷类 Qt项目视图提供了一些便捷类,包括QListWidget, QTableWidget, QTreeWidget等。我们分别介绍这几个便捷类。 我们先创建一个Qt …...
git worktree的使用
git worktree 是 Git 提供的一个强大功能,允许你在同一个仓库中同时创建多个工作目录,每个目录对应一个分支,从而实现并行开发。以下是 git worktree 的常用命令和使用方法: 1. 创建新的工作目录(Worktree)…...
Spring Boot+RabbitMQ+Canal 解决数据一致性
目录大纲 一、环境配置1.1 docker-compose.yml 配置1.2 docker-compose 常用命令1.3 镜像服务启动状态 二、MySQL binlog 配置2.1 docker-compose command 配置 binlog2.2 创建canal用户,以及查看是否开启binlog 三、canal 相关配置文件3.1 canal.properties 完整文…...
Java高频面试之集合-08
hello啊,各位观众姥爷们!!!本baby今天来报道了!哈哈哈哈哈嗝🐶 面试官:详细说说CopyOnWriteArrayList CopyOnWriteArrayList 详解 CopyOnWriteArrayList 是 Java 并发包(java.util…...
C#实现高性能异步文件下载器(支持进度显示/断点续传)
一、应用场景分析 异步文件下载器用处很大,当我们需要实现以下功能时可以用的上: 大文件下载(如4K视频/安装包) 避免UI线程阻塞,保证界面流畅响应多任务并行下载 支持同时下载多个文件,提升带宽利用率后台…...
【数据分析】转录组基因表达的KEGG通路富集分析教程
禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍差异分析(limma)KEGG富集分析(enrichKEGG)可视化加载R包数据下载导入数据基因差异分析火山图KEGG通路富集分析可视化通路结果另一个案例总结系统信息参考介绍 KEGG富集分析,可…...
【由技及道】API契约的量子纠缠术:响应封装的十一维通信协议(全局的返回结果封装)【人工智障AI2077的开发日志012】
摘要:在API通信的量子混沌中,30种返回格式如同平行宇宙的物理定律相互碰撞。本文构建的十一维通信协议,通过时空锚点(ApiResult)、量子过滤器(ResponseWrapper)和湮灭防护罩(Jackson…...
STM32 ——系统架构
3个被动单元 SRAM 存储程序运行时用到的变量 Flash(内部闪存存储器) 存储下载的程序 程序执行时用到的常量 桥接1和桥接2 AHB到APB的桥(AHBtoAPBx) 桥1 通过APB2总线连接到APB2上的外设。 高速外设,最高72MHz。 桥2 通过…...
算法 之 树形dp 树的中心、重心
文章目录 重心实践题目小红的陡峭值 在树的算法中,求解树的中心和重心是一类十分重要的算法 求解树的重心 树的重心的定义:重心是树中的一个节点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点…...
如何利用 Excel 表格实现精准文件批量重命名教程
在处理大量文件时,有时需要根据特定规则对文件名进行调整。如果您的文件名和新名称之间存在一对多的关系,并且这种关系可以通过 Excel 表格来管理,那么使用“简鹿文件批量重命名”软件中的“匹配对应名称命名”功能将是一个高效的选择。接下来…...
ACE协议学习1
在多核系统或复杂SoC(System on Chip)中,不同处理器核心或IP(Intellectual Property)模块之间需要保持数据的一致性。常用的是ACE协议or CHI。 先对ACE协议进行学习 ACE协议(Advanced Microcontroller Bu…...
装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器
一.自适应梯度算法Adagrad概述 Adagrad(Adaptive Gradient Algorithm)是一种自适应学习率的优化算法,由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率,适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...
vscode(仍待补充)
写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh? debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...
