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

LeetCode 0685.冗余连接 II:并查集(和I有何不同分析)——详细题解(附图)

【LetMeFly】685.冗余连接 II:并查集(和I有何不同分析)——详细题解(附图)

力扣题目链接:https://leetcode.cn/problems/redundant-connection-ii/

在本问题中,有根树指满足以下条件的 有向 图。该树只有一个根节点,所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点,而根节点没有父节点。

输入一个有向图,该图由一个有着 n 个节点(节点值不重复,从 1n)的树及一条附加的有向边构成。附加的边包含在 1n 中的两个不同顶点间,这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi],用以表示 有向 图中连接顶点 ui 和顶点 vi 的边,其中 uivi 的一个父节点。

返回一条能删除的边,使得剩下的图是有 n 个节点的有根树。若有多个答案,返回最后出现在给定二维数组的答案。

 

示例 1:

输入:edges = [[1,2],[1,3],[2,3]]
输出:[2,3]

示例 2:

输入:edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]
输出:[4,1]

 

提示:

  • n == edges.length
  • 3 <= n <= 1000
  • edges[i].length == 2
  • 1 <= ui, vi <= n

解题方法:并查集

并查集

解题思路

这题和684.冗余连接的区别是:

684的无向图只需要考虑有没有形成自环,而本题有向图还需要考虑“是否形成了入度为2的节点”。

如果形成了“入度为2”的节点,例如下面两种情况,在684.冗余连接中只需要移除“首次形成(无向)环”的边,而在685.冗余连接II中就不能只移除“最后出现的导致形成(无向)环的边”:

1----->2      1------+
↑      ↑      ↑      ↓
3------+      2<-----3<---4

左图中只能移除[1,2][3,2]而不能移除[3,1];右图中只能移除[1,3]而不能移除[3,2][2,1]

有向边不能和无向边一概而论的本质原因是:树中一个节点不能有两个父节点,即入度不能为2。所以,一旦出现了入度为2的节点 n o d e node node,就要在“终点为 n o d e node node的两条边”里面选择一条移除。判断方法如下:

尝试移除一条边,判断剩下的边(不考虑方向)能否构成无向环,如果不构成无向环则说明这条边可以被移除。

判断方法就和684题一模一样了,使用并查集即可完成判断。

树上多一条边就一定存在入度为2的节点吗?不一定,还可能有以下这种情况:

1------+
↑      ↓
2<-----3----->4

图中节点[1,2,3]形成了一个环,但12344个节点的入度都为1

这样就和684题一模一样了其实,在环[1,2,3]里任意移除一条边图都能变成树。

同样使用并查集,返回第一条“形成环”的边即为所求。

解题方法

首先统计是否有入度为2的节点:

  • 若有,则尝试移除指向2的边(若移除后图中无环则这条边可以被移除)
  • 否则,移除第一条导致“环出现”的边

常见问题回答Q&A

Q1: 若有入度为2的节点,在判断“移除一条边后图是否为树”时,能否通过“统计每个点是否孤立(入度出度都为0)”来判断?

例如下图中终点为3的边有[1,3][4,3]两条,移除[4,3]的话会导致点4成为孤立点,因此只能移除[1,3]

1------+
↑      ↓
2<-----3<---4

A1: 不能这么判断。例如下图只能移除[2,4]不能移除[5,2],但其实移除其中的任意一条都不会产生“孤立点”。

+---+
↓   ↑
4-->2↑
1-->5-->3

建议修改为“通过判断图是否联通”的方式判断某条边是否可以移除。

时空复杂度

  • 时间复杂度最坏 O ( n log ⁡ n ) O(n\log n) O(nlogn),平均为 O ( n α ( n ) ) O(n\alpha(n)) O(nα(n))(接近 O ( n ) O(n) O(n)
  • 空间复杂度 O ( n ) O(n) O(n)

AC代码

C++
class Solution {
private:vector<int> fa;bool couldRemoveThisEdge(vector<vector<int>>& edges, int index) {initFa(edges.size());for (int i = 0; i < edges.size(); i++) {if (i == index) {continue;}if (find(edges[i][0]) == find(edges[i][1])) {return false;}union_(edges[i][0], edges[i][1]);}return true;}vector<int> solution_indegree(vector<vector<int>>& edges, int node) {for (int i = edges.size() - 1; i >= 0; i--) {if (edges[i][1] == node && couldRemoveThisEdge(edges, i)) {return edges[i];}}return {};  // FAKE RETURN}int find(int x) {if (x != fa[x]) {fa[x] = find(fa[x]);}return fa[x];}void union_(int x, int y) {fa[find(x)] = find(y);}void initFa(int n) {fa.resize(n + 1);for (int i = 1; i <= n; i++) {fa[i] = i;}}vector<int> solution_unionFind(vector<vector<int>>& edges) {initFa(edges.size());for (vector<int>& edge : edges) {if (find(edge[0]) == find(edge[1])) {return edge;} else {union_(edge[0], edge[1]);}}return {};  // FAKE RETURN}
public:vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {vector<bool> inDegree(edges.size() + 1);for (vector<int>& edge : edges) {if (inDegree[edge[1]]) {  // 找到了入度为2的点return solution_indegree(edges, edge[1]);} else {inDegree[edge[1]] = true;}}return solution_unionFind(edges);}
};
Python
from typing import Listclass Solution:def initFa(self) -> None:for i in range(1, len(self.edges) + 1):self.fa[i] = idef find(self, x: int) -> int:if self.fa[x] != x:self.fa[x] = self.find(self.fa[x])return self.fa[x]def union(self, x: int, y: int) -> None:self.fa[self.find(x)] = self.find(y)def couldRemoveThisEdge(self, index: int) -> bool:self.initFa()for i in range(len(self.edges)):if i == index:continueif self.find(self.edges[i][0]) == self.find(self.edges[i][1]):return Falseelse:self.union(self.edges[i][0], self.edges[i][1])return Truedef solution_indegree(self, node: int) -> List[int]:for i in range(len(self.edges) - 1, -1, -1):if self.edges[i][1] == node and self.couldRemoveThisEdge(i):return self.edges[i]return []  # FAKE RETURNdef solution_unionFind(self) -> List[int]:self.initFa()for x, y in self.edges:if self.find(x) == self.find(y):return [x, y]else:self.union(x, y)return []  # FAKE RETURNdef findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:self.fa = [0] * (len(edges) + 1)self.edges = edgeshasIndegree = [False] * (len(edges) + 1)for x, y in edges:if hasIndegree[y]:return self.solution_indegree(y)else:hasIndegree[y] = Truereturn self.solution_unionFind()
Java
class UnionFind {private int[] fa;public UnionFind(int n) {fa = new int[n + 1];for (int i = 1; i <= n; i++) {fa[i] = i;}}private int find(int x) {if (fa[x] != x) {fa[x] = find(fa[x]);}return fa[x];}public boolean isUnion(int x, int y) {return find(x) == find(y);}public void union(int x, int y) {fa[find(x)] = find(y);}
}class Solution {private boolean canRemoveThisEdge(int[][] edges, int index) {UnionFind unionFind = new UnionFind(edges.length);for (int i = 0; i < edges.length; i++) {if (i == index) {continue;}if (unionFind.isUnion(edges[i][0], edges[i][1])) {return false;} else {unionFind.union(edges[i][0], edges[i][1]);}}return true;}private int[] solution_indegree(int[][] edges, int node) {for (int i = edges.length - 1; i >= 0; i--) {if (edges[i][1] == node && canRemoveThisEdge(edges, i)) {return edges[i];}}return new int[0];  // FAKE RETURN}private int[] solution_unionFind(int[][] edges) {UnionFind unionFind = new UnionFind(edges.length);for (int[] edge : edges) {if (unionFind.isUnion(edge[0], edge[1])) {return edge;} else {unionFind.union(edge[0], edge[1]);}}return new int[0];  // FAKE RETURN}public int[] findRedundantDirectedConnection(int[][] edges) {boolean[] hasIndegree = new boolean[edges.length + 1];for (int[] edge : edges) {if (hasIndegree[edge[1]]) {return solution_indegree(edges, edge[1]);} else {hasIndegree[edge[1]] = true;}}return solution_unionFind(edges);}
}
Go
package maintype UnionFind struct {fa []int
}func New(n int) UnionFind {fa := make([]int, n + 1)for th, _ := range fa {fa[th] = th}return UnionFind{fa}
}func (unionFind UnionFind) _find(x int) int {if unionFind.fa[x] != x {unionFind.fa[x] = unionFind._find(unionFind.fa[x])}return unionFind.fa[x]
}func (unionFind UnionFind) isUnion(x, y int) bool {return unionFind._find(x) == unionFind._find(y)
}func (unionFind UnionFind) union(x, y int) {unionFind.fa[unionFind._find(x)] = unionFind._find(y)
}func canRemoveThisEdge(edges [][]int, index int) bool {unionFind := New(len(edges))for i := 0; i < len(edges); i++ {if i == index {continue}if unionFind.isUnion(edges[i][0], edges[i][1]) {return false} else {unionFind.union(edges[i][0], edges[i][1])}}return true
}func solution_indegree(edges [][]int, node int) []int {for i := len(edges) - 1; i >= 0; i-- {if edges[i][1] == node && canRemoveThisEdge(edges, i) {return edges[i]}}return make([]int, 0)  // FAKE RETURN
}func solution_unionFind(edges [][]int) []int {unionFind := New(len(edges))for _, edge := range edges {if unionFind.isUnion(edge[0], edge[1]) {return edge} else {unionFind.union(edge[0], edge[1])}}return make([]int, 0)  // FAKE RETURN
}func findRedundantDirectedConnection(edges [][]int) []int {hasIndegree := make([]bool, len(edges) + 1)for _, edge := range edges {if hasIndegree[edge[1]] {return solution_indegree(edges, edge[1])} else {hasIndegree[edge[1]] = true}}return solution_unionFind(edges)
}

同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~

Tisfy:https://letmefly.blog.csdn.net/article/details/143470538

相关文章:

LeetCode 0685.冗余连接 II:并查集(和I有何不同分析)——详细题解(附图)

【LetMeFly】685.冗余连接 II&#xff1a;并查集&#xff08;和I有何不同分析&#xff09;——详细题解(附图) 力扣题目链接&#xff1a;https://leetcode.cn/problems/redundant-connection-ii/ 在本问题中&#xff0c;有根树指满足以下条件的 有向 图。该树只有一个根节点&…...

Dubbo负载均衡

负载均衡策略与配置细节 Dubbo 内置了 client-based 负载均衡机制&#xff0c;如下是当前支持的负载均衡算法&#xff0c;结合上文提到的自动服务发现机制&#xff0c;消费端会自动使用 Weighted Random LoadBalance 加权随机负载均衡策略 选址调用。 如果要调整负载均衡算法…...

PymuPDF4llm提取pdf文件文字、表格与图片

一、PymuPDF4llm 的功能特点 &#xff08;一&#xff09;文本提取 简单易用 PymuPDF4llm 的文本提取功能非常简单易用。只需使用pip install pymupdf4llm进行安装&#xff0c;然后通过import pymupdf4llm导入库&#xff0c;就可以使用md_text pymupdf4llm.to_markdown("…...

20241108通过iperf3确认中科创达的高通CM6125的WIFI的网速【失败】

20241108通过iperf3确认中科创达的高通CM6125的WIFI的网速【失败】 2024/11/8 15:43 由于以太网不能用&#xff0c;那就测试一下WIFI&#xff0c;iperf3链接/测试异常。 一般认为可能的原因有&#xff1a; 1、CM6125开发板的WIFI不带天线&#xff0c;影响性能。 2、CM6125的And…...

Stored procedures in PostgreSQL

select 存储过程&#xff0c;在现了解的情况&#xff0c;还是没有mysql,sqlserver等好写好用。 --postgreSQL 11.0 以下版本 create or replace FUNCTION procInsertSchool (pSchoolId Char(5),pSchoolName VarChar(100),pSchoolTelNo VarChar(8) ) RETURNS void language plp…...

第10章 多表查询

一、什么是多表查询 多表查询&#xff0c;也称为关联查询&#xff0c;指两个或更多个表一起完成查询操作。 前提条件&#xff1a;这些一起查询的表之间是有关系的&#xff08;一对一、一对多&#xff09;&#xff0c;它们之间一定是有关联字段&#xff0c;这个关联字段可能建立…...

【基于LSM的ELF文件安全模块设计】参考

《基于LSM的ELF文件安全模块设计文档》 一、设计目标 本设计致力于通过 Linux 安全模块&#xff08;LSM&#xff09;构建一个强大而严密的安全防护体系&#xff0c;以实现对 ELF 文件&#xff08;涵盖可执行文件和动态链接库&#xff09;的绝对严格的合法性和完整性检查。其核…...

全卷积和全连接

全连接网络和全卷积网络不一样 以下是对两者的正确解释和代码示例&#xff1a; 1. 全连接网络&#xff08;Fully Connected Network&#xff09; 全连接网络使用的是 线性层&#xff08;nn.Linear&#xff09;&#xff0c;也就是我们常说的“全连接层”。它是用于将每一个输入…...

Unity图形学之Shader结构

Unity - Manual: ShaderLab: Legacy Lighting 1.Shader 语言&#xff1a; OpenGL&#xff1a;SGL 跨平台性能非常好 GLSL语言 OpenGL Shader LanguageDX&#xff1a;微软 非跨平台 性能非常好 HLSL语言 High Level Shader LanguageCG&#xff1a;微软和英伟达 联合开发CG …...

离散时间信号的产生

文章目录 前言1.单位冲激序列函数1.2 函数&#xff1a;1.3 实现代码&#xff1a;1.3 调用方式1.4 调用结果 2.单位阶跃序列函数2.1 函数2.2实现代码2.3调用方式2.4调用结果 3.矩形序列3.1函数3.2 实现代码3.3调用方式3.4 调用结果 4.实指数序列4.1函数4.2实现代码4.3调用方式4.…...

物联优化汽车齿轮锻造

在汽车齿轮的锻造工艺中&#xff0c;锻造温度、锻造压力与行程、锻造速度与锤击方式以及热处理工艺等核心参数扮演着举足轻重的角色。这些参数的精准控制与实时监测&#xff0c;对于提升生产效率、确保产品质量、削减生产成本以及推动生产智能化转型具有不可估量的价值。明达技…...

CocosCreator 构建透明背景应用(最新版!!!)

文章目录 透明原理补充设置截图以及代码step1: electron-js mian.jsstep2:ENABLE_TRANSPARENT_CANVASstep3:SOLID_COLOR Transparentstep:4 Build Web phonestep5:package electron-js & change body background-color 效果图补充 透明原理 使用Cocos creator 做桌面应用开…...

使用CentOS宝塔面板docker搭建EasyTier内网穿透服务

0. 前言 EasyTier是一个简单、安全、去中心化的内网穿透 VPN 组网方案&#xff0c;部署方便&#xff0c;支持 MacOS/Linux/Windows/FreeBSD/Android平台&#xff0c;而且作者搭建了一个公共服务器&#xff0c;不想折腾自建服务&#xff0c;可以使用默认的公共服务器地址 tcp:/…...

HTMLCSS: 实现可爱的冰墩墩

效果演示 HTML <div class"wrap"><div class"body"></div><div class"ear"></div><div class"ear rightEar"></div><div class"leftHand"></div><div class"…...

天地图入门|标注|移动飞行|缩放,商用地图替换

“天地图”是国家测绘地理信息局建设的地理信息综合服务网站。集成了来自国家、省、市&#xff08;县&#xff09;各级测绘地理信息部门&#xff0c;以及相关政府部门、企事业单位 、社会团体、公众的地理信息公共服务资源&#xff0c;如果做的项目是政府部门、企事业单位尽量选…...

Flutter PC端UI组件库

一、参考Element-ui的设计和交互&#xff0c;构建基于dart的Flutter UI组件库 https://javonhuang.github.io/sky-ui-page/index.html...

NVR小程序接入平台/设备EasyNVR多品牌NVR管理工具/设备汇聚公共资源场景方案全析

随着信息技术的飞速发展&#xff0c;视频监控已经成为现代社会安全管理和业务运营不可或缺的一部分。特别是在公共资源管理方面&#xff0c;视频监控的应用日益广泛&#xff0c;涵盖了智慧城市、智能交通、大型企业以及校园安防等多个领域。NVR小程序接入平台EasyNVR作为一款功…...

干部谈话考察系统:革新传统,精准高效

在干部选拔任用和考核评价的过程中&#xff0c;谈话考察一直是关键环节之一。然而&#xff0c;传统的谈话考察方式却面临着诸多痛点&#xff0c;严重影响了干部考察工作的质量和效率。干部谈话考察系统的出现&#xff0c;为解决这些问题提供了有力的武器。 一、传统谈话考察的…...

反转链表(Leetcode)

反转链表 Leetcode题目链接 题意&#xff1a;翻转一个单链表 &#x1f330;: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 在链表本身进行反转即可&#xff0c;不用重新定义链表&#xff0c;这同时浪费时间和空间。 需要采用哑…...

制作游戏外挂的技术栈有哪些

制作游戏外挂是一项涉及多方面技术的复杂任务。这项技术通常被用于在游戏中获得不公平的优势&#xff0c;因此也遭到了大量的讨论与争议。制作外挂需要深厚的编程基础、对系统底层的深入理解以及对具体游戏架构的详细研究。以下是一篇全面的分析文章&#xff0c;旨在揭示制作游…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

FFmpeg avformat_open_input函数分析

函数内部的总体流程如下&#xff1a; avformat_open_input 精简后的代码如下&#xff1a; int avformat_open_input(AVFormatContext **ps, const char *filename,ff_const59 AVInputFormat *fmt, AVDictionary **options) {AVFormatContext *s *ps;int i, ret 0;AVDictio…...

实战设计模式之模板方法模式

概述 模板方法模式定义了一个操作中的算法骨架&#xff0c;并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下&#xff0c;重新定义算法中的某些步骤。简单来说&#xff0c;就是在一个方法中定义了要执行的步骤顺序或算法框架&#xff0c;但允许子类…...

聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇

根据 QYResearch 发布的市场报告显示&#xff0c;全球市场规模预计在 2031 年达到 9848 万美元&#xff0c;2025 - 2031 年期间年复合增长率&#xff08;CAGR&#xff09;为 3.7%。在竞争格局上&#xff0c;市场集中度较高&#xff0c;2024 年全球前十强厂商占据约 74.0% 的市场…...

ThreadLocal 源码

ThreadLocal 源码 此类提供线程局部变量。这些变量不同于它们的普通对应物&#xff0c;因为每个访问一个线程局部变量的线程&#xff08;通过其 get 或 set 方法&#xff09;都有自己独立初始化的变量副本。ThreadLocal 实例通常是类中的私有静态字段&#xff0c;这些类希望将…...

从实验室到产业:IndexTTS 在六大核心场景的落地实践

一、内容创作&#xff1a;重构数字内容生产范式 在短视频创作领域&#xff0c;IndexTTS 的语音克隆技术彻底改变了配音流程。B 站 UP 主通过 5 秒参考音频即可克隆出郭老师音色&#xff0c;生成的 “各位吴彦祖们大家好” 语音相似度达 97%&#xff0c;单条视频播放量突破百万…...