当前位置: 首页 > 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…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...

LangFlow技术架构分析

&#x1f527; LangFlow 的可视化技术栈 前端节点编辑器 底层框架&#xff1a;基于 &#xff08;一个现代化的 React 节点绘图库&#xff09; 功能&#xff1a; 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...