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

代码随想录算法训练营第六十一天 | 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. 冗余连接 题目链接&#xff1a;KamaCoder 文档讲解&#xff1a;代码随想录 状态&#xff1a;AC Java代码&#xff1a; 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”。 本文提出一种可扩展、自下而上且本质多样化的数据收集方案&#xff0c;该方案可用于长期和中期的高级推理&#xff0c;与传统的狭窄自上而下的逐步收集相比&#xff0c…...

TCP/IP原理详细解析

前言 TCP/IP是一种面向连接&#xff0c;可靠的传输&#xff0c;传输数据大小无限制的。通常情况下&#xff0c;系统与系统之间的http连接需要三次握手和四次挥手&#xff0c;这个执行过程会产生等待时间。这方面在日常开发时需要注意一下。 TCP/IP 是互联网的核心协议族&…...

Microsof Visual Studio Code 安装教程(中文设置)

VS Code 是一个免费的代码编辑器&#xff0c;可在 macOS、Linux 和 Windows作系统上运行。启动和运行 VS Code 既快速又简单。VS Code&#xff08;全称 Visual Studio Code&#xff09;是一款由Microsoft 推出的免费、开源、跨平台的代码编辑器&#xff0c;拥有强大的功能和灵活…...

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&#xff08;面向数据的技术堆栈&#xff09;是一套由 Unity 提供支持的技术&#xff0c;用于提供高性能游戏开发解决方案&#xff0c;特别适合需要处理大量数据的游戏&#xff0c;例如大型开放世…...

linux 软件安装(上)

一、基础环境准备 1.1、安装VM 1.2、在VM上导入linux iso镜像&#xff0c;装好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时的问题及权限处理方法

访问站点&#xff0c;提示如下 No input file specified. 可能是文件权限有问题&#xff0c;也可能是“.user.ini”文件路径没有配置对&#xff0c;最简单的办法就是直接将它删除掉&#xff0c;还有就是将它设置正确 #配置成自己服务器上正确的路径 open_basedir/mnt/qiy/te…...

【江协科技STM32】ADC数模转换器-学习笔记

ADC简介 ADC&#xff08;Analog-Digital Converter&#xff09;模拟-数字转换器ADC可以将引脚上连续变化的模拟电压转换为内存中存储的数字变量&#xff0c;建立模拟电路到数字电路的桥梁&#xff0c;ADC是一种将连续的模拟信号转换为离散的数字信号的设备或模块12位逐次逼近型…...

QT系列教程(20) Qt 项目视图便捷类

视频连接 https://www.bilibili.com/video/BV1XY41127t3/?vd_source8be9e83424c2ed2c9b2a3ed1d01385e9 Qt项目视图便捷类 Qt项目视图提供了一些便捷类&#xff0c;包括QListWidget, QTableWidget&#xff0c; QTreeWidget等。我们分别介绍这几个便捷类。 我们先创建一个Qt …...

git worktree的使用

git worktree 是 Git 提供的一个强大功能&#xff0c;允许你在同一个仓库中同时创建多个工作目录&#xff0c;每个目录对应一个分支&#xff0c;从而实现并行开发。以下是 git worktree 的常用命令和使用方法&#xff1a; 1. 创建新的工作目录&#xff08;Worktree&#xff09…...

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用户&#xff0c;以及查看是否开启binlog 三、canal 相关配置文件3.1 canal.properties 完整文…...

Java高频面试之集合-08

hello啊&#xff0c;各位观众姥爷们&#xff01;&#xff01;&#xff01;本baby今天来报道了&#xff01;哈哈哈哈哈嗝&#x1f436; 面试官&#xff1a;详细说说CopyOnWriteArrayList CopyOnWriteArrayList 详解 CopyOnWriteArrayList 是 Java 并发包&#xff08;java.util…...

C#实现高性能异步文件下载器(支持进度显示/断点续传)

一、应用场景分析 异步文件下载器用处很大&#xff0c;当我们需要实现以下功能时可以用的上&#xff1a; 大文件下载&#xff08;如4K视频/安装包&#xff09; 避免UI线程阻塞&#xff0c;保证界面流畅响应多任务并行下载 支持同时下载多个文件&#xff0c;提升带宽利用率后台…...

【数据分析】转录组基因表达的KEGG通路富集分析教程

禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍差异分析(limma)KEGG富集分析(enrichKEGG)可视化加载R包数据下载导入数据基因差异分析火山图KEGG通路富集分析可视化通路结果另一个案例总结系统信息参考介绍 KEGG富集分析,可…...

【由技及道】API契约的量子纠缠术:响应封装的十一维通信协议(全局的返回结果封装)【人工智障AI2077的开发日志012】

摘要&#xff1a;在API通信的量子混沌中&#xff0c;30种返回格式如同平行宇宙的物理定律相互碰撞。本文构建的十一维通信协议&#xff0c;通过时空锚点&#xff08;ApiResult&#xff09;、量子过滤器&#xff08;ResponseWrapper&#xff09;和湮灭防护罩&#xff08;Jackson…...

STM32 ——系统架构

3个被动单元 SRAM 存储程序运行时用到的变量 Flash&#xff08;内部闪存存储器&#xff09; 存储下载的程序 程序执行时用到的常量 桥接1和桥接2 AHB到APB的桥&#xff08;AHBtoAPBx) 桥1 通过APB2总线连接到APB2上的外设。 高速外设&#xff0c;最高72MHz。 桥2 通过…...

算法 之 树形dp 树的中心、重心

文章目录 重心实践题目小红的陡峭值 在树的算法中&#xff0c;求解树的中心和重心是一类十分重要的算法 求解树的重心 树的重心的定义&#xff1a;重心是树中的一个节点&#xff0c;如果将这个点删除后&#xff0c;剩余各个连通块中点数的最大值最小&#xff0c;那么这个节点…...

如何利用 Excel 表格实现精准文件批量重命名教程

在处理大量文件时&#xff0c;有时需要根据特定规则对文件名进行调整。如果您的文件名和新名称之间存在一对多的关系&#xff0c;并且这种关系可以通过 Excel 表格来管理&#xff0c;那么使用“简鹿文件批量重命名”软件中的“匹配对应名称命名”功能将是一个高效的选择。接下来…...

ACE协议学习1

在多核系统或复杂SoC&#xff08;System on Chip&#xff09;中&#xff0c;不同处理器核心或IP&#xff08;Intellectual Property&#xff09;模块之间需要保持数据的一致性。常用的是ACE协议or CHI。 先对ACE协议进行学习 ACE协议&#xff08;Advanced Microcontroller Bu…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...