有向图的强连通分量——AcWing 367. 学校网络
有向图的强连通分量
定义
强连通分量(Strongly Connected Components, SCC) 是图论中的一个概念,在一个有向图中,如果存在一个子图,使得该子图中的任意两个顶点都相互可达(即从任何一个顶点出发都可以到达该子图中的其他任何顶点),那么这个子图就称为一个强连通分量。注意,这里的“子图”指的是原图的一个极大子集,也就是说,它不能被扩展成更大的满足上述条件的集合。
运用情况
- 网络分析:在互联网路由、社交网络分析中识别紧密相连的群体。
- 编译器优化:在程序流图中找到可以独立优化的部分。
- 数据挖掘:在有向无环图(DAG)中寻找循环依赖。
- 游戏设计:确定游戏中不同关卡之间的关系。
注意事项
- 强连通分量的求解通常需要考虑图的大小和复杂度,对于大规模图可能需要高效算法。
- 非强连通的有向图可以被分解为其强连通分量的集合,这些分量之间形成一个有向无环图(DAG),这有助于理解图的结构。
解题思路
- Kosaraju's 算法:这是一种两遍深度优先搜索算法。首先对原图进行一次深度优先搜索,记录下每个顶点的完成时间;然后构建原图的转置图,并按照第一次DFS的完成时间逆序遍历顶点,对转置图进行第二次深度优先搜索。每次新的DFS遍历开始时找到的顶点集合就是一个强连通分量。
- Tarjan's 算法:这是另一种使用深度优先搜索的方法,但是它是单遍的。它利用低链接值(low-link value)的概念来发现强连通分量。
AcWing 367. 学校网络
题目描述
367. 学校网络 - AcWing题库

运行代码
#include <cstring>
#include <iostream>
using namespace std;
const int N = 110, M = N * N;
int n;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int din[N], dout[N];
int scc_cnt, id[N];
int stk[N], top;
bool in_stk[N];void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}void tarjan(int u)
{dfn[u] = low[u] = ++ timestamp;stk[ ++ top] = u, in_stk[u] = true;for(int i = h[u]; ~i; i = ne[i]){int j = e[i];if(!dfn[j]){tarjan(j);low[u] = min(low[u], low[j]);}else if(in_stk[j])low[u] = min(low[u], dfn[j]);}if(low[u] == dfn[u]){int y;scc_cnt ++ ;do{y = stk[top -- ];in_stk[y] = false;id[y] = scc_cnt;}while(y != u);}
}int main()
{memset(h, -1, sizeof h);cin >> n;for(int i = 1; i <= n; i ++ ){int t;while(cin >> t, t) add(i, t);}for(int i = 1; i <= n; i ++ ) if(!dfn[i])tarjan(i);for(int i = 1; i <= n; i ++ )for(int j = h[i]; ~j; j = ne[j]){int k = e[j];int a = id[i], b = id[k];if(a != b){dout[a] ++ ;din[b] ++ ;}}int a = 0, b = 0; for(int i = 1; i <= scc_cnt; i ++ ){if(!din[i]) a ++ ;if(!dout[i]) b ++ ;}cout << a << endl;if(scc_cnt == 1) puts("0");else cout << max(a, b) << endl;return 0;
}
代码思路
-
初始化图结构: 使用邻接表表示有向图,
h[]数组存储每个顶点的首条边的索引,e[]数组存储边的目的顶点,ne[]数组存储每条边的下一条边的索引。 -
深度优先搜索(DFS):
- 使用
dfn[]数组存储顶点的访问顺序(发现时间)。 - 使用
low[]数组存储能够回溯到的最早发现时间。 - 使用
stk[]数组和in_stk[]数组跟踪DFS栈中的顶点,用于检测强连通分量。 tarjan()函数递归地执行DFS,并更新low[]数组,当low[u] == dfn[u]时,表明找到了一个新的强连通分量。
- 使用
-
强连通分量后处理:
- 计算每个强连通分量的入度(
din[])和出度(dout[])。 - 统计没有入度或没有出度的强连通分量数量,即潜在的入口点或出口点。
- 计算每个强连通分量的入度(
-
输出结果:
- 输出没有入度的强连通分量数量作为潜在入口点数。
- 如果整个图是一个强连通分量,则输出0,否则输出入口点和出口点的最大数量。
改进思路
-
内存效率:可以使用
vector代替数组来动态分配空间,减少不必要的预分配。 -
代码清晰性:分离图的构建、强连通分量检测和后处理逻辑,增加可读性和可维护性。
-
异常处理:增加输入验证,确保输入格式正确,避免潜在的运行时错误。
-
性能优化:考虑使用更高效的容器类型,如
std::unordered_map来加速查找操作(虽然在这个特定问题上可能不会显著影响性能)。 -
多源点和多汇点检测:直接输出没有入度或出度的SCC数量可能不足以描述图的特性,可以考虑输出具体的SCC信息。
相关文章:
有向图的强连通分量——AcWing 367. 学校网络
有向图的强连通分量 定义 强连通分量(Strongly Connected Components, SCC) 是图论中的一个概念,在一个有向图中,如果存在一个子图,使得该子图中的任意两个顶点都相互可达(即从任何一个顶点出发都可以到达该子图中的其他任何顶点…...
安全开发--多语言基础知识
注释:还是要特别说明一下,想成为专业开发者不要看本文,本文是自己从业安全以来的一些经验总结,所有知识点也只限于网络安全这点事儿,再多搞不明白了。 开发语言 笼统的按照是否编译成机器码分类开发语言,…...
如何使一个盒子水平垂直居中(常用的)
目录 1. 使用Flex布局 2. 使用Grid布局 3.绝对定位 负外边距 (必须知晓盒子的具体大小) 4.绝对定位外边距 auto 5.绝对定位 transform (无须知晓盒子的具体大小) 1. 使用Flex布局 如何实现: 在父元素上添加: display: flex; align-items: center…...
安全防御-用户认证综合实验
一、拓扑图 二、实验要求 1、DMZ区的服务器,办公区仅能在办公时间内(9:00-18:00)可以访问,生产区设备全天都是可以访问的 2、生产区不允许访问互联网,办公区和游客区允许访问互联网 3、办公区设备10.0.2.20不允许访…...
uniapp安卓离线打包配置scheme url
uniapp安卓离线打包配置scheme url 打开 AndroidManifest.xml 搜索 scheme 填入 即可 <?xml version"1.0" encoding"utf-8"?> <manifest xmlns:android"http://schemas.android.com/apk/res/android" package"uni.UNI979A394…...
C++ STL std::lexicographical_compare用法和实现
一:功能 按字典顺序比较两个序列,判断第一个序列是否小于(或大于)第二个序列 二:用法 #include <compare> #include <vector> #include <string> #include <algorithm> #include <iostream> #include <fo…...
ORM Bee,如何使用Oracle的TO_DATE函数?
ORM Bee,如何使用Oracle的TO_DATE函数? 在Bee V2.4.0,可以这样使用: LocaldatetimeTable selectBeannew LocaldatetimeTable();Condition conditionBF.getCondition();condition.op("localdatetime", Op.ge, new TO_DATE("2024-07-08", "YYYY-MM-DD&…...
HTML CSS 基础复习笔记 - 框架、装饰、弹性盒子
自己复习前端基础,仅用于记忆,初学者不太适合 示例代码 - HTML <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initi…...
C++:创建线程
在C中创建线程,最直接的方式是使用C11标准引入的<thread>库。这个库提供了std::thread类,使得线程的创建和管理变得简单直接。 以下是一个简单的示例,展示了如何在C中使用std::thread来创建和启动线程: 示例1:…...
python如何查看类的函数
Python非常方便,它不需要用户查询文档,只需掌握如下两个帮助函数,即可查看Python中的所有函数(方法)以及它们的用法和功能: dir():列出指定类或模块包含的全部内容(包括函数、方法、…...
P6. 对局列表和排行榜功能
P6. 对局列表和排行榜功能 0 概述1 对局列表功能1.1 分页配置1.2 后端按页获取对局列表接口1.3 前端展示传回来的对局列表1.4 录像回放功能1.4.1 录像回放的流程1.4.2 录像回放的实现 1.5 前端分页展示 2 排行榜功能2.1 排行榜的实现 0 概述 本节主要介绍了如何实现对局列表和…...
uniapp easycom组件冲突
提示信息 easycom组件冲突:[/components/uni-icons/uni-icons.vue,/uni_modules/uni-icons/components/uni-icons/uni-icons.vue] 问题描述 老项目,在uniapp插件商城导入了一个新的uniapp官方开发的组件》uni-data-picker 数据驱动的picker选择器 …...
总结24个Python接单赚钱平台与详细教程,兼职月入5000+
如果说当下什么编程语言最靠谱或者比较适合搞副业? 答案肯定100%是:Python。 python是所有语法中最简单易上手的语言,不需要特别的的英语词汇量,逻辑思维也不需要很差就能上手。而且学会了之后就能编写代码爬取各种数据…...
macOS 的电源适配器设置
在 macOS 的电源适配器设置中,有四个选项,每个选项都有特定的功能: Prevent your Mac from automatically sleeping when the display is off(当显示屏关闭时,防止你的 Mac 自动进入睡眠状态):…...
视觉SLAM与定位之一前端特征点及匹配
视觉SLAM中的特征点及匹配 参考文章或链接特征点性能的评估传统特征点和描述子(仅特征点或者特征点描述子)传统描述子 基于深度学习的特征点基于深度学习的描述子基于深度学习的特征点描述子特征匹配 参考文章或链接 Image Matching from Handcrafted t…...
开源项目的认识理解
目录 开源项目有哪些机遇与挑战? 1.开源项目的发展趋势 2.开源的经验分享(向大佬请教与上网查询) 3.开源项目的挑战 开源项目有哪些机遇与挑战? 1.开源项目的发展趋势 1. 持续增长与普及 - 开源项目将继续增长,…...
37.哀家要长脑子了!--层序遍历
gongmi层序遍历模板 vector<vector<int>> levelOrder(TreeNode *root){queue<TreeNode*> que;vector<vector<int>> res;if(root ! nullptr)que.push(root);while(!que.empty()){int size que.size();vector<int> storey;for(int i 0; i …...
【从零开始AI绘画6】StableDiffusionWebUI拓展的安装方法以及推荐的几个拓展
这里写自定义目录标题 拓展Extention安装方法(以双语对照插件为例)1、WebUI内置的下载方式(推荐)2、git clone安装(更推荐)3、github下载安装包后解压(不推荐) 强力推荐安装的几个插…...
HTML5表单的自动验证、取消验证、自定义错误信息
1、自动验证 通过在元素中使用属性的方法,该属性可以实现在表单提交时执行自动验证的功能。下面是关于对元素内输入内容进行限制的属性的指定。 属性说明required输入内容是否不为空pattern输入的内容是否符合指定格式min、max输入的数值是否在min~max范围step判断…...
SpringMVC系列九: 数据格式化与验证及国际化
SpringMVC 数据格式化基本介绍基本数据类型和字符串自动转换应用实例-页面演示方式Postman完成测试 特殊数据类型和字符串自动转换应用实例-页面演示方式Postman完成测试 验证及国际化概述应用实例代码实现注意事项和使用细节 注解的结合使用先看一个问题解决问题 数据类型转换…...
React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...
【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...
Docker拉取MySQL后数据库连接失败的解决方案
在使用Docker部署MySQL时,拉取并启动容器后,有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致,包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因,并提供解决方案。 一、确认MySQL容器的运行状态 …...
基于鸿蒙(HarmonyOS5)的打车小程序
1. 开发环境准备 安装DevEco Studio (鸿蒙官方IDE)配置HarmonyOS SDK申请开发者账号和必要的API密钥 2. 项目结构设计 ├── entry │ ├── src │ │ ├── main │ │ │ ├── ets │ │ │ │ ├── pages │ │ │ │ │ ├── H…...
