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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/463512.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

mysql查表相关练习

作业要求&#xff1a; 单表练习&#xff1a; 1 . 查询出部门编号为 D2019060011 的所有员工 2 . 所有财务总监的姓名、编号和部门编号。 3 . 找出奖金高于工资的员工。 4 . 找出奖金高于工资 40% 的员工。 5 找出部门编号为 D2019090011 中所有财务总监&#xff0c;和…

GHuNeRF: Generalizable Human NeRF from a Monocular Video

研究背景 研究问题&#xff1a;这篇文章要解决的问题是学习一个从单目视频中泛化的人类NeRF模型。尽管现有的泛化人类NeRF已经取得了令人印象深刻的成果&#xff0c;但它们需要多视图图像或视频&#xff0c;这在某些情况下可能不可用。此外&#xff0c;一些基于单目视频的人类…

Linux - grep的正则用法

新建u.txt&#xff0c;文本内容如图&#xff1a; 搜寻特定字符串 利用中括号[]搜寻集合字符 行首与行位字符^$ 任意一个字符.与重复字符*限定连续RE字符范围{} 总结:

项目模块十五:HttpResponse模块

一、模块设计思路 存储HTTP应答要素&#xff0c;提供简单接口 二、成员变量 int _status; // 应答状态码 unordered_map<string, string> _headers; // 报头字段 string _body; // 应答正文 bool _redirect_flag; // 是否重定向信息 stri…

从零开始的c++之旅——继承

1. 继承 1.继承概念及定义 继承是面向对象编程的三大特点之一&#xff0c;它使得我们可以在原有类特性的基础之上&#xff0c;增加方法 和属性&#xff0c;这样产生的新的类&#xff0c;称为派生类。 继承 呈现了⾯向对象程序设计的层次结构&#xff0c;以前我们接触的…

6.1、实验一:静态路由

源文件获取&#xff1a;6.1_实验一&#xff1a;静态路由.pkt: https://url02.ctfile.com/f/61945102-1420248902-c5a99e?p2707 (访问密码: 2707) 一、目的 理解路由表的概念 会使用基础命令 根据需求正确配置静态路由 二、准备实验 1.实验要求 让PC0、PC1、PC2三台电脑…

logback日志级别动态切换四种方案

生产环境中经常有需要动态修改日志级别。 现在就介绍几种方案 方案一&#xff1a;开启logback的自动扫描更新 配置如下 <?xml version"1.0" encoding"UTF-8"?> <configuration scan"true" scanPeriod"60 seconds" debug…

Qt字符编码

目前字符编码有以下几种&#xff1a; 1、UTF-8 UTF-8编码是Unicode字符集的一种编码方式(CEF)&#xff0c;其特点是使用变长字节数(即变长码元序列、变宽码元序列)来编码。一般是1到4个字节&#xff0c;当然&#xff0c;也可以更长。 2、UTF-16 UTF-16是Unicode字符编码五层次…

postman 获取登录接口中的返回token并设置为环境变量的方法 postman script

postman是一个比较方便的API开发调试工具&#xff0c; 我们在访问API时一般都需要设置一个token来对服务进行认证&#xff0c; 这个token一般都是通过登录接口来获取。 这个postman脚本放到登录接口的sctipt--> post-response里面即可将登陆接口中返回的token值设置到postma…

使用Django REST framework构建RESTful API

使用Django REST framework构建RESTful API Django REST framework简介 安装Django REST framework 创建Django项目 创建Django应用 配置Django项目 创建模型 迁移数据库 创建序列化器 创建视图 配置URL 配置全局URL 配置认证和权限 测试API 使用Postman测试API 分页 过滤和排序…

消息队列面试——打破沙锅问到底

消息队列的面试连环炮 前言 你用过消息队列么&#xff1f;说说你们项目里是怎么用消息队列的&#xff1f; 我们有一个订单系统&#xff0c;订单系统会每次下一个新订单的时候&#xff0c;就会发送一条消息到ActiveMQ里面去&#xff0c;后台有一个库存系统&#xff0c;负责获取…

Rust 力扣 - 1493. 删掉一个元素以后全为 1 的最长子数组

文章目录 题目描述题解思路题解代码题目链接 题目描述 题解思路 本题我们能转换成求只包含一个0的子数组的最长长度 如果数组中不存在0&#xff0c;则结果为数组长度减一 我们使用一个left指针指向子数组的左边界&#xff0c;然后我们遍历子数组的右边界&#xff0c;我们记录…

在 Windows 系统上,在两台机器上测试 MySQL 集群实现实时备份的基本步骤:

在两台机器上测试 MySQL 集群实现实时备份的基本步骤&#xff1a; 一、环境准备 机器配置 确保两台机器&#xff08;假设为服务器 A 和服务器 B&#xff09;能够互相通信&#xff0c;例如它们在同一个局域网内&#xff0c;并且开放了 MySQL 通信所需的端口&#xff08;默认是 3…

常见的开源软件许可证及其应用案例

目录 引言 开源的定义 开源许可证的种类 常见的开源许可证及其应用案例 结论 引言 开源软件在过去几十年中迅速发展&#xff0c;已经成为软件开发的重要组成部分。开源不仅仅是一种技术模式&#xff0c;更是一种文化和社区精神。本文将详细介绍开源的定义、开源许可证的种…

校招回顾 | “青春不散场,梦想正起航”,极限科技(INFINI Labs)亮相湖北工业大学 2025 秋季校园招聘会

10 月 31 日&#xff0c;极限科技&#xff08;INFINI Labs&#xff09; 受邀参加 湖北工业大学 2025 届秋季校园招聘会&#xff0c;这不仅是一次与满怀激情的青年学子们的深度碰撞&#xff0c;更是一场关于青春与未来的美好邂逅。让我们一起回顾校招现场的精彩瞬间&#xff0c;…

基于python的机器学习(一)—— 基础知识(Scikit-learn安装)

目录 一、机器学习基础 1.1 机器学习概述 1.2 监督学习、无监督学习和强化学习 1.3 聚类、分类、回归、标注 1.3.1 聚类 1.3.2 分类 1.3.3 回归 1.3.4 标注 1.4 机器学习、人工智能和数据挖掘 1.5 机器学习的三个要素 二、Scikit-learn 机器学习库 2.1 Scikit-lea…

第五篇: 使用Python和BigQuery进行电商数据分析与可视化

使用Python和BigQuery进行电商数据分析与可视化 大数据分析对于电商业务的洞察至关重要。在这篇文章中&#xff0c;我们将使用Python结合Google BigQuery来分析电商数据集&#xff0c;以最畅销商品和平均订单价格最高的前10位客户为主题&#xff0c;展示如何通过数据可视化提供…

基于SpringBoot+Vue的快递物流信息查询系统设计与实现【前后端分离】

基于SpringBootVue的快递物流信息查询系统设计与实现 摘要 随着电子商务的快速发展&#xff0c;快递物流系统的重要性愈发突出。针对用户对快递信息的实时查询需求&#xff0c;本系统结合Spring Boot和Vue技术&#xff0c;设计并实现了一个高效、易用的快递物流信息查询系统。系…

开源免费的API网关介绍与选型

api网关的主要作用 API网关在现代微服务架构中扮演着至关重要的角色&#xff0c;它作为内外部系统通信的桥梁&#xff0c;不仅简化了服务调用过程&#xff0c;还增强了系统的安全性与可管理性。例如&#xff0c;当企业希望将内部的服务开放给外部合作伙伴使用时&#xff0c;直…

WPF+MVVM案例实战(十七)- 自定义字体图标按钮的封装与实现(ABC类)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 1、案例效果1、按钮分类2、ABC类按钮实现1、文件创建2、字体图标资源3、自定义依赖属性4、按钮特效样式实现 3、按钮案例演示1、页面实现与文件创建2、依赖注入3 运…