【图论】【 割边】【C++算法】1192. 查找集群内的关键连接

2024-03-28 18:20

本文主要是介绍【图论】【 割边】【C++算法】1192. 查找集群内的关键连接,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

作者推荐

视频算法专题

本文涉及知识点

图论 割边
割边和割点类似,DFS(next)的返回值 如果小于等于time[cur] 则不是割边。
割点原理及封装好的割点类(预计2024年3月11号左右发布)

LeetCoce1192. 查找集群内的关键连接

力扣数据中心有 n 台服务器,分别按从 0 到 n-1 的方式进行了编号。它们之间以 服务器到服务器 的形式相互连接组成了一个内部集群,连接是无向的。用 connections 表示集群网络,connections[i] = [a, b] 表示服务器 a 和 b 之间形成连接。任何服务器都可以直接或者间接地通过网络到达任何其他服务器。
关键连接 是在该集群中的重要连接,假如我们将它移除,便会导致某些服务器无法访问其他服务器。
请你以任意顺序返回该集群内的所有 关键连接 。

示例 1:

输入:n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
输出:[[1,3]]
解释:[[3,1]] 也是正确的。
示例 2:

输入:n = 2, connections = [[0,1]]
输出:[[0,1]]

提示:
2 <= n <= 105
n - 1 <= connections.length <= 105
0 <= ai, bi <= n - 1
ai != bi
不存在重复的连接

代码

核心代码

class CNeiBo
{
public:	static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) {vector<vector<int>>  vNeiBo(n);for (const auto& v : edges){vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);if (!bDirect){vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);}}return vNeiBo;}	static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0){vector<vector<std::pair<int, int>>> vNeiBo(n);for (const auto& v : edges){vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);if (!bDirect){vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);}}return vNeiBo;}static vector<vector<int>> Grid(int rCount, int cCount, std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext){vector<vector<int>> vNeiBo(rCount * cCount);auto Move = [&](int preR, int preC, int r, int c){if ((r < 0) || (r >= rCount)){return;}if ((c < 0) || (c >= cCount)){return;}if (funVilidCur(preR, preC) && funVilidNext(r, c)){vNeiBo[cCount * preR + preC].emplace_back(r * cCount + c);}};for (int r = 0; r < rCount; r++){for (int c = 0; c < cCount; c++){Move(r, c, r + 1, c);Move(r, c, r - 1, c);Move(r, c, r, c + 1);Move(r, c, r, c - 1);}}return vNeiBo;}
};//割点
class CCutPoint
{
public:CCutPoint(const vector<vector<int>>& vNeiB) : m_iSize(vNeiB.size()){m_vNodeToTime.assign(m_iSize, -1);m_vCutNewRegion.resize(m_iSize);		}void Init(const vector<vector<int>>& vNeiB){for (int i = 0; i < m_iSize; i++){if (-1 == m_vNodeToTime[i]){m_vRegionFirstTime.emplace_back(m_iTime);dfs(vNeiB, i, -1);}}}	const int m_iSize;const vector<int>& Time()const { return m_vNodeToTime; }//各节点的时间戳const vector<int>& RegionFirstTime()const { return m_vRegionFirstTime; }//各连通区域的最小时间戳vector<bool> CalCut()const { vector<bool> ret;for (int i = 0; i < m_iSize; i++){ret.emplace_back(m_vCutNewRegion[i].size());}return ret; }//const vector < vector<pair<int, int>>>& NewRegion()const { return m_vCutNewRegion; };
protected:int dfs(const vector<vector<int>>& vNeiB, const int cur, const int parent){int iMinTime = m_vNodeToTime[cur] = m_iTime++;OnBeginDFS(cur);int iRegionCount = (-1 != parent);//根连通区域数量for (const auto& next : vNeiB[cur]) {if (next == parent){continue;}if (-1 != m_vNodeToTime[next]) {iMinTime = min(iMinTime, m_vNodeToTime[next]);continue;}const int childMinTime = dfs(vNeiB, next, cur);iMinTime = min(iMinTime, childMinTime);if (childMinTime >= m_vNodeToTime[cur]) {iRegionCount++;m_vCutNewRegion[cur].emplace_back(m_vNodeToTime[next], m_iTime);}OnVisitNextEnd(childMinTime,cur, next);}if (iRegionCount < 2){m_vCutNewRegion[cur].clear();}return iMinTime;}virtual void OnVisitNextEnd(int childMinTime,int cur, int next) {};virtual void OnBeginDFS(int cur) {};vector<int> m_vNodeToTime;vector<int> m_vRegionFirstTime;vector < vector<pair<int, int>>> m_vCutNewRegion; //m_vCutNewRegion[c]如果存在[left,r) 表示割掉c后,时间戳[left,r)的节点会形成新区域int m_iTime = 0;
};class CCutEdge : public CCutPoint
{
public:using CCutPoint::CCutPoint;vector<vector<int>> m_vCutEdges;
protected:virtual void OnVisitNextEnd(int childMinTime, int cur, int next) override {if (childMinTime > m_vNodeToTime[cur]){m_vCutEdges.emplace_back(vector<int>{ cur,next });}}
};class Solution {
public:vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {auto neiBo = CNeiBo::Two(n, connections, false);CCutEdge cut(neiBo);cut.Init(neiBo);return cut.m_vCutEdges;}
};

测试用例


template<class T, class T2>
void Assert(const T& t1, const T2& t2)
{assert(t1 == t2);
}template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){Assert(v1[i], v2[i]);}}int main()
{int n;vector<vector<int>> connections;{Solution sln;n = 2, connections = { {0,1} };auto res = sln.criticalConnections(n, connections);Assert({ { 0,1} }, res);}{Solution sln;n = 4, connections = { {0,1},{1,2},{2,0},{1,3} };auto res = sln.criticalConnections(n, connections);Assert({ { 1,3} }, res);}
}

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

这篇关于【图论】【 割边】【C++算法】1192. 查找集群内的关键连接的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/856362

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if(staticif),:本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa

Spring Boot 整合 MyBatis 连接数据库及常见问题

《SpringBoot整合MyBatis连接数据库及常见问题》MyBatis是一个优秀的持久层框架,支持定制化SQL、存储过程以及高级映射,下面详细介绍如何在SpringBoot项目中整合My... 目录一、基本配置1. 添加依赖2. 配置数据库连接二、项目结构三、核心组件实现(示例)1. 实体类2. Ma

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

电脑win32spl.dll文件丢失咋办? win32spl.dll丢失无法连接打印机修复技巧

《电脑win32spl.dll文件丢失咋办?win32spl.dll丢失无法连接打印机修复技巧》电脑突然提示win32spl.dll文件丢失,打印机死活连不上,今天就来给大家详细讲解一下这个问题的解... 不知道大家在使用电脑的时候是否遇到过关于win32spl.dll文件丢失的问题,win32spl.dl

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.