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

图论17-有向图的强联通分量-Kosaraju算法

文章目录

  • 1 概念
  • 2 Kosaraju算法
    • 2.1 在图类中设计反图
    • 2.2 强连通分量的判断和普通联通分量的区别
    • 2.3 代码实现

1 概念

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

2 Kosaraju算法

对原图的反图进行DFS的后序遍历。
在这里插入图片描述
在这里插入图片描述

2.1 在图类中设计反图

// 重写图的构造函数public Graph(TreeSet<Integer>[] adj, boolean directed){this.adj = adj;this.directed = directed;this.V = adj.length;this.E = 0;indegrees = new int[V];outdegrees = new int[V];for(int v = 0; v < V; v ++)for(int w: adj[v]){outdegrees[v] ++;indegrees[w] ++;this.E ++;}if(!directed) this.E /= 2;}// 求反图,并且new一个图对象,参数为TreeSetpublic Graph reverseGraph(){TreeSet<Integer>[] rAdj = new TreeSet[V];for(int i = 0; i < V; i ++)rAdj[i] = new TreeSet<Integer>();for(int v = 0; v < V; v ++)for(int w : adj(v))rAdj[w].add(v);return new Graph(rAdj, directed);}

2.2 强连通分量的判断和普通联通分量的区别

强联通分量是环,意味着在DFS过程中一定是公用相同的联通分量序号。

当这个环遍历从环尾开始返回并记录ccid的时候,DFS自由返回到环, 索引指向下一个未被访问过的环外的节点,此时联通分量序号+1。 由于图是反过来的。

单步调试一下更容易理解。

在这里插入图片描述

2.3 代码实现

顶点:注意这里遍历的顺序是反过来的图。

并且,对翻转过来的图进行DFS后序遍历

        GraphDFS dfs = new GraphDFS(G.reverseGraph());ArrayList<Integer> order = new ArrayList<>();for(int v: dfs.post())order.add(v);Collections.reverse(order);for(int v: order) //注意这里遍历的顺序是反过来的图if(visited[v] == -1){dfs(v, scccount);scccount ++;}

但是在DFS的时候,判断邻边用的是原来的邻接列表。

    private void dfs(int v, int sccid){visited[v] = sccid;for(int w: G.adj(v))if(visited[w] == -1)dfs(w, sccid);}

相关文章:

图论17-有向图的强联通分量-Kosaraju算法

文章目录 1 概念2 Kosaraju算法2.1 在图类中设计反图2.2 强连通分量的判断和普通联通分量的区别2.3 代码实现 1 概念 2 Kosaraju算法 对原图的反图进行DFS的后序遍历。 2.1 在图类中设计反图 // 重写图的构造函数public Graph(TreeSet<Integer>[] adj, boolean dire…...

ubuntu中使用 vscode 连接docker开发环境

文章目录 ubuntu中使用 vscode 连接docker开发环境步骤一&#xff1a;安装 Remote Development 插件步骤二&#xff1a;连接远程环境步骤三&#xff1a;开发 问题解决参考连接 ubuntu中使用 vscode 连接docker开发环境 Remote Development 是一个 Visual Studio Code 插件&…...

【广州华锐视点】海外制片人VR虚拟情景教学带来全新的学习体验

虚拟现实&#xff08;Virtual Reality&#xff0c;简称VR&#xff09;是一种利用电脑模拟产生一个三维的虚拟世界&#xff0c;提供用户关于视觉、听觉、触觉等感官的模拟体验的技术。随着科技的进步&#xff0c;VR已经被广泛应用到许多领域&#xff0c;包括游戏、教育、医疗、房…...

龙芯loongarch64麒麟服务器配置yum源

服务器信息&#xff1a; uname -a # 命令 Linux bogon 4.19.90-52.22.v2207.a.ky10.loongarch64 #1 SMP Tue Mar 14 11:18:26 CST 2023 loongarch64 loongarch64 loongarch64 GNU/Linux yum源配置&#xff1a; cd /etc/yum.repos.d/ vim kylin_loongarch64.repo 将下面内容拷贝…...

Centos7 单用户模式修改密码 3步搞定 666 (百分比成功)

1.第一步重新服务器 2.进入这个页面按e进入单用户模式 3.找到linux16这行 在后面添加 init/bin/bash 按ctrlx进入 4.注意是事项直接修改是报错passud: Authentication token manipulation error 需要执行权限&#xff1a;mount -o remount,rw /...

深度学习 机器视觉 车位识别车道线检测 - python opencv 计算机竞赛

0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 深度学习 机器视觉 车位识别车道线检测 该项目较为新颖&#xff0c;适合作为竞赛课题方向&#xff0c;学长非常推荐&#xff01; &#x1f947;学长这里给一个题目综合评分(每项满分5分) …...

Java主流分布式解决方案多场景设计与实战

Java的主流分布式解决方案的设计和实战涉及到多个场景&#xff0c;包括但不限于以下几点&#xff1a; 分布式缓存&#xff1a;在Java的分布式系统中&#xff0c;缓存是非常重要的一部分。常用的分布式缓存技术包括Redis、EhCache等。这些缓存技术可以用来提高系统的性能和响应…...

docker安装MongoDB数据库,并且进行密码配置

很美的一首小诗> 我在外面流浪&#xff0c;回来时 故乡瘦了一圈—— 墩子叔走了&#xff0c;门前的池水 干了一半。 屋后驼背的柳树 头发散落了一地&#xff0c; 老房子蹲在坟边&#xff0c;屋顶的白云 仍在风中奔跑。 安装配置 要在Docker中安装MongoDB并启用远程连接&…...

ssh脚本找不到命令或者执行无效的解决办法

如图&#xff1a;今天在编写脚本时发现的这个问题&#xff0c; 在排除脚本语法错误、编码格式等情况下&#xff0c;仍然出现“bash 。。未找到命令”的字样 解决办法&#xff1a; 给每台虚拟机的环境变量source一下&#xff1a; 命令如下 source /etc/profile或者输入 vim ~…...

2023年11月18日(星期六)骑行海囗林场公园

2023年11月18日 (星期六) 骑行海囗林场公园(赏枫树林&#xff09;&#xff0c;早8:30到9:00&#xff0c; 大观公园门囗集合&#xff0c;9:30准时出发 【因迟到者&#xff0c;骑行速度快者&#xff0c;可自行追赶偶遇。】 偶遇地点:大观公园门口集合 &#xff0c;家住东&#x…...

xss 漏洞

1、XSS类型 XSS攻击大致上分为3类&#xff1a; 反射型xss&#xff0c;DOM型xss&#xff0c;存储型xss。前两类为非持久性xss&#xff0c;后者为持久型xss。 1.1 非持久型xss&#xff1a; 1&#xff09;反射型 XSS 攻击相对于访问者而言是一次性的&#xff0c;具体表现在恶意…...

一文图解爬虫_姊妹篇(spider)

—引导语 爬虫&#xff0c;没有一个时代比当前更重视它。一个好的爬虫似乎可以洞穿整个互联网&#xff0c;“来装满自己的胃”。 接上一篇&#xff1a;一文图解爬虫&#xff08;spider&#xff09; 博主已初步对爬虫的“五脏六腑”进行了解剖。虽然俗称“爬虫”&#xff0c;但窃…...

【vue实战项目】通用管理系统:api封装、404页

前言 本文为博主的vue实战小项目系列中的第三篇&#xff0c;很适合后端或者才入门的小伙伴看&#xff0c;一个前端项目从0到1的保姆级教学。前面的内容&#xff1a; 【vue实战项目】通用管理系统&#xff1a;登录页-CSDN博客 【vue实战项目】通用管理系统&#xff1a;封装to…...

R语言编写代码示例

R语言编写的爬虫程序&#xff0c;使用了requests库来发送请求&#xff0c;使用BeautifulSoup库来解析HTML。 r # 第一步&#xff0c;安装必要的库 install.packages("xml2") install.packages("requests") install.packages("httr") install.pac…...

[RK3568][Android12.0]--- 系统自带预置第三方APK方法

Platform: RK3568 OS: Android 12.0 Kernel: 4.19 Rockchip默认提供了机制来预置第三方APK, 方法很简单&#xff1a; 1. 在device/rockchip/rk3568创建preinstall目录(如果要可卸载&#xff0c;那就创建preinstall_del目录) 2. 将你要预安装的APK放进此目录即可 preinstall 不…...

数据分析场景下,企业如何做好大模型选型和落地?

在数据驱动的数字化时代&#xff0c;有效的数据分析已成为企业成功的关键因素。而随着大模型带来能力突破&#xff0c;让AI与数据分析相互结合&#xff0c;使分析结果更好支撑业务&#xff0c;促进企业内部数据价值释放&#xff0c;成为了当下企业用户尤为关注的话题。 如何按照…...

使用VScode编译betaflight固件--基于windows平台

使用VScode编译betaflight固件--基于windows平台 1、使用git克隆betaflight的开源代码2、betaflight的代码框架分析&#xff1a;3、配置编译环境&#xff1a;4、VScode上编译 betaflight不仅可以在LInux上进行编译也可以在Windows上编译&#xff0c;本文主要介绍在windows平台上…...

OkHttp网络请求读写超时

查看OkHttp的源码&#xff1a; OkHttpClient 的 Builder() public Builder() {...callTimeout 0;connectTimeout 10_000;readTimeout 10_000;writeTimeout 10_000;... } callTimeout&#xff1a;整个请求的超时时间&#xff0c;如果设置了这个值&#xff0c;则总超时时间…...

@postmapping 定义formdata传参方式

背景&#xff1a;feign声明接口&#xff0c;传对象&#xff0c; 但是对象那边没有用requestBody接收&#xff1b; 前端调它也是走的formdata&#xff0c;所以不改变源代码&#xff0c;以及补新接口的情况下&#xff0c;我也需要formdata传参&#xff1b; 不然数据传不过去会为空…...

Windows客户端开发框架WPF简介

一、WPF简介 WPF的全称是Windows Presentation Foundation&#xff0c;WPF是 Microsoft 提供的一种用于构建桌面应用程序的 UI 框架。它包含在 .NET Framework 中&#xff0c;从 .NET 3.0 版本开始就被引入。 以下是一些关于 WPF 的关键特性&#xff1a; 1. XAML&#xff1a…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...