LeetCode 684.冗余连接:拓扑排序+哈希表(O(n)) 或 并查集(O(nlog n)-O(nα(n)))

【LetMeFly】684.冗余连接:拓扑排序+哈希表(O(n)) 或 并查集(O(nlog n)-O(nα(n)))

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

树可以看成是一个连通且 无环 的 无向 图。

给定往一棵 n 个节点 (节点值 1~n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1n 中间,且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ,edges[i] = [ai, bi] 表示图中在 aibi 之间存在一条边。

请找出一条可以删去的边,删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案,则返回数组 edges 中最后出现的那个。

 

示例 1:

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

示例 2:

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

 

提示:

  • n == edges.length
  • 3 <= n <= 1000
  • edges[i].length == 2
  • 1 <= ai < bi <= edges.length
  • ai != bi
  • edges 中无重复元素
  • 给定的图是连通的 

方法一:拓扑排序(哈希表)

记录每个点的度,使用拓扑排序的思想,每次将度为1的节点所连的边移除。

最后剩下的点就是“环”中的点,将这些点放入哈希表中。

倒叙遍历“边”,第一条两个节点都出现在哈希表中的边即为所求。

  • 时间复杂度 O ( n ) O(n) O(n)
  • 空间复杂度 O ( n ) O(n) O(n)

AC代码

C++
class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        vector<int> degree(edges.size() + 1);
        vector<vector<int>> graph(edges.size() + 1);
        for (vector<int>& edge : edges) {
            degree[edge[0]]++;
            degree[edge[1]]++;
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        queue<int> q;
        for (int i = 1; i <= edges.size(); i++) {
            if (degree[i] == 1) {
                q.push(i);
            }
        }
        while (q.size()) {
            int thisNode = q.front();
            q.pop();
            for (int nextNode : graph[thisNode]) {
                degree[nextNode]--;
                if (degree[nextNode] == 1) {
                    q.push(nextNode);
                }
            }
        }
        unordered_set<int> reservedNodes;
        for (int i = 1; i <= edges.size(); i++) {
            if (degree[i] > 1) {
                reservedNodes.insert(i);
            }
        }
        // for (vector<vector<int>>::iterator it = edges.rbegin(); it != edges.rend(); it++)
        for (int i = edges.size() - 1; i >= 0; i--) {
            if (reservedNodes.count(edges[i][0]) && reservedNodes.count(edges[i][1])) {
                return edges[i];
            }
        }
        return {};  // FAKE RETURN
    }
};

方法二:并查集

使用并查集将每条边的两个顶点加入同一个集合中,第一条两个顶点已经在一个集合中的边即为所求(加上这条边后就形成了环)。

  • 时间复杂度 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;

    int find(int x) {
        if (fa[x] != x) {
            fa[x] = find(fa[x]);
        }
        return fa[x];
    }

    void union_(int x, int y) {
        fa[find(x)] = find(y);
    }
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        fa.resize(edges.size() + 1);
        for (int i = 1; i <= edges.size(); i++) {
            fa[i] = i;
        }
        // for (vector<int>& edge : edges) {
        //     union_(edge[0], edge[1]);
        // }
        // for (int i = edges.size() - 1; i > 0; i--) {
        //     if (find(edges[i][0]) == find(edges[i][1])) {
        //         return edges[i];
        //     }
        // }
        for (vector<int>& edge : edges) {
            if (find(edge[0]) == find(edge[1])) {
                return edge;
            } else {
                union_(edge[0], edge[1]);
            }
        }
        return {};  // FAKE RETURN
    }
};
Python
from typing import List

class Solution:
    def union(self, x: int, y: int) -> None:
        self.fa[self.find(x)] = self.find(y)
    
    def find(self, x: int) -> int:
        if self.fa[x] != x:
            self.fa[x] = self.find(self.fa[x])
        return self.fa[x]

    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        self.fa = [i for i in range(len(edges) + 1)]
        for x, y in edges:
            if self.find(x) == self.find(y):
                return [x, y]
            else:
                self.union(x, y)
        return []  # FAKE RETURN

Java
class Solution {
    private int[] fa;

    private int find(int x) {
        if (fa[x] != x) {
            fa[x] = find(fa[x]);
        }
        return fa[x];
    }

    private void union(int x, int y) {
        fa[find(x)] = find(y);
    }

    public int[] findRedundantConnection(int[][] edges) {
        fa = new int[edges.length + 1];
        for (int i = 1; i <= edges.length; i++) {
            fa[i] = i;
        }
        for (int[] edge : edges) {
            if (find(edge[0]) == find(edge[1])) {
                return edge;
            } else {
                union(edge[0], edge[1]);
            }
        }
        return new int[0];
    }
}
Go
package main

func find(fa []int, x int) int {
    if fa[x] != x {
        fa[x] = find(fa, fa[x])
    }
    return fa[x]
}

func union(fa []int, x int, y int) {
    fa[find(fa, x)] = find(fa, y)
}

func findRedundantConnection(edges [][]int) []int {
    fa := make([]int, len(edges) + 1)
    for th, _ := range fa {
        fa[th] = th
    }
    for _, edge := range edges {
        if find(fa, edge[0]) == find(fa, edge[1]) {
            return edge
        } else {
            union(fa, edge[0], edge[1])
        }
    }
    return nil
}

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

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

今晚(20241102晚10:30)这会儿api.github.com似乎出了点问题,国内外都访问不到X_X

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

数字IC后端实现之Innovus Place跑完density爆涨案例分析

下图所示为咱们社区a7core后端训练营学员的floorplan。 数字IC后端实现 | Innovus各个阶段常用命令汇总 该学员跑placement前density是59.467%&#xff0c;但跑完place后density飙升到87.68%。 仔细查看place过程中的log就可以发现Density一路飙升&#xff01; 数字IC后端物…

项目管理软件:5款甘特图工具测评

在项目管理中&#xff0c;甘特图作为一种直观且高效的任务进度展示工具&#xff0c;被广泛应用于各个行业。以下是几款功能强大、易于使用的甘特图工具&#xff0c;它们能够帮助项目经理更好地规划、跟踪和管理项目进度。 1、进度猫 进度猫是国内项目管理新秀&#xff0c;是…

MYSQL 真实高并发下的死锁

https://pan.baidu.com/s/1nM3VQdbkNZhnK-wWboEYxA?pwdvwu6 下面是风控更新语句 ------------------------ LATEST DETECTED DEADLOCK ------------------------ 2023-08-04 01:00:10 140188779017984 *** (1) TRANSACTION: TRANSACTION 895271870, ACTIVE 0 sec starting …

CTFshow之信息收集第11关到20关。详细讲解

得而不惜就该 --小阁老 新篇章的接续&#xff01; 一、实验准备 1、ctf网站&#xff1a;ctf.show 2、工具&#xff1a;chrome浏览器、hackbar插件 3、burpsuite抓包工具 二、实验技巧 &#xff08;一&#xff09;域名与子域名的dns解析记录 &#xff08;二&#xff09…

【论文复现】语言模型中的多模态链式推理

&#x1f4d5;作者简介&#xff1a;热爱跑步的恒川&#xff0c;致力于C/C、Java、Python等多编程语言&#xff0c;热爱跑步&#xff0c;喜爱音乐、摄影的一位博主。 &#x1f4d7;本文收录于论文复现系列&#xff0c;大家有兴趣的可以看一看 &#x1f4d8;相关专栏C语言初阶、C…

Docker:网络 Network

Docker&#xff1a;网络 Network Docker 网络架构CNMLibnetwork驱动网络类型 命令docker network lsdocker network inspectdocker network createdocker network connectdocker network disconnectdocker network prunedocker network rm 网络操作bridgehostcontainernone Doc…

局部敏感哈希(LSH)简介

0. Intro \textbf{0. Intro} 0. Intro 1️⃣ LSH \text{LSH} LSH的优势&#xff1a;在 λ \lambda{} λ较大的度量空间&#xff0c;也可以高效回答 c-ANN \text{c-ANN} c-ANN查询问题 2️⃣一些预备知识 多重集并集 (multi-set union): \text{(multi-set union): } (multi-set…

论文 | Evaluating the Robustness of Discrete Prompts

论文《Evaluating the Robustness of Discrete Prompts》深入探讨了离散提示&#xff08;Discrete Prompts&#xff09;的鲁棒性&#xff0c;即离散提示在自然语言处理任务中面对不同扰动时的表现。研究特别关注离散提示在自然语言推理&#xff08;NLI&#xff09;任务中的表现…

Linux 之 信号概念、进程、进程间通信、线程、线程同步

学习任务&#xff1a; 1、 信号&#xff1a;信号的分类、进程对信号的处理、向进程发送信号、信号掩码 2、 进程&#xff1a;进程与程序的概念、进程的内存布局、进程的虚拟地址空间、fork创建子进程、wait监视子进程 3、 学习进程间通信&#xff08;管道和FIFO、信号、消息队列…

Vue:模板 MVVM

Vue&#xff1a;模板 & MVVM 模板插值语法指令语法 MVVMdefineProperty数据代理 模板 Vue实例绑定一个容器&#xff0c;想要向容器中填入动态的值&#xff0c;就需要使用模板语法。模板语法分为插值语法和指令语法。 插值语法 插值语法很简单&#xff0c;使用{{}}包含一…

C++中的继承——第二篇

一、继承与友元 友元关系不能够继承&#xff08;就像父亲的朋友不一定是自己的朋友&#xff09; 具体实现起来就是父类的友元可以访问父类的成员&#xff0c;但是不可以访问子类的成员 二、继承与静态成员 子类的静态成员变量本质上与父类的是同一份&#xff0c;存储在静态…

uni-app发起请求以及请求封装,上传及下载功能(六)

文章目录 一、发起网络请求1.使用及封装2. https 请求配置自签名证书3.拦截器 二、上传下载1.上传 uni.uploadFile(OBJECT)2. 下载 uni.downloadFile(OBJECT) 一、发起网络请求 uni-app中内置的uni.request()已经很强大了&#xff0c;简单且好用。为了让其更好用&#xff0c;同…

SLAM定位总结

文章目录 一、激光定位1.A-LOAM &#xff08;2018&#xff09;2.F-LOAM &#xff08;2021&#xff09;3.CT-ICP &#xff08;2022&#xff09;3.DLO:Fast Localization with Dense Point Clouds &#xff08;2022&#xff09;4.kiss-ICP :In Defense of Point-to-Point ICP Sim…

大端存储和小端存储

大端存储和小端存储 在计算机系统中&#xff0c;数据在内存中的存储方式并不是唯一的。对于多字节的数据类型&#xff08;如 int、float 等&#xff09;&#xff0c;计算机可以以不同的方式在内存中存储它们。这些存储方式通常分为两种&#xff1a;大端存储&#xff08;Big-En…

【数据结构二叉树】C非递归算法实现二叉树的先序、中序、后序遍历

引言: 遍历二叉树&#xff1a;指按某条搜索路径巡访二叉树中每个结点&#xff0c;使得每个结点均被访问一次&#xff0c;而且仅被访问一次。 除了层次遍历外&#xff0c;二叉树有三个重要的遍历方法&#xff1a;先序遍历、中序遍历、后序遍历。 1、递归算法实现先序、中序、后…

【LeetCode】移除链表中等于设定值的元素、反转链表

主页&#xff1a;HABUO&#x1f341;主页&#xff1a;HABUO &#x1f31c;有时候世界虽然是假的&#xff0c;但并不缺少真心对待我们的人&#x1f31b; 1. 移除链表中设定值的元素 题目&#xff1a;给你一个链表的头节点 head 和一个整数 val &#xff0c;请你删除链表中所…

程序员日志之DNF手游1023版本活动补充

目录 传送门正文日志1、概要2、正文 传送门 SpringMVC的源码解析&#xff08;精品&#xff09; Spring6的源码解析&#xff08;精品&#xff09; SpringBoot3框架&#xff08;精品&#xff09; MyBatis框架&#xff08;精品&#xff09; MyBatis-Plus SpringDataJPA SpringClo…

macOS开发环境配置与应用开发教程

macOS开发环境配置与应用开发教程 引言 macOS是一个强大的操作系统&#xff0c;广泛应用于软件开发&#xff0c;尤其是iOS和macOS应用开发。本文将详细介绍如何配置macOS开发环境&#xff0c;并通过实例演示如何进行应用开发。希望通过这篇文章&#xff0c;帮助读者快速上手m…

提高交换网络可靠性之认识STP根桥与端口角色

转载请注明出处 该实验旨在学习如何选举根桥与识别端口角色。 1.三台交换机按要求连线&#xff0c;改名&#xff0c;分别为S1&#xff0c;S2&#xff0c;S3&#xff0c;以S1为例&#xff1a; 2.在S1上配置优先级为28672 同理&#xff0c;在交换机S2和S3上配置其优先级为32768&…

基于大数据的热门旅游景点数据分析系统的设计与实现

作者主页&#xff1a;编程千纸鹤 作者简介&#xff1a;Java领域优质创作者、CSDN博客专家 、CSDN内容合伙人、掘金特邀作者、阿里云博客专家、51CTO特邀作者、多年架构师设计经验、多年校企合作经验&#xff0c;被多个学校常年聘为校外企业导师&#xff0c;指导学生毕业设计并参…