【图论】强连通分量
一.定义
![]()
强连通分量(Strongly Connected Components,简称SCC)是图论中的一个概念,用于描述有向图中的一组顶点,其中任意两个顶点之间都存在一条有向路径。换句话说,对于图中的任意两个顶点u和v,如果存在一条从u到v的有向路径,同时也存在一条从v到u的有向路径,那么u和v就属于同一个强连通分量。
强连通分量在许多图算法中都有重要的应用,比如强连通分量的计算可以用于解决图的可达性问题、强连通分量的缩点可以用于求解最小生成树等。
注意:强连通分量是有向图!
二.例题
P2661 [NOIP2015 提高组] 信息传递 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
三.思路
我们可以易知可以求得最小环即可。也可以说要求最小强连通分量。
这里可以用tarjan算法实现
四.参考代码
#include<bits/stdc++.h>
#define maxn 200005
using namespace std;
int n,dfn[maxn],low[maxn],tot;
//链式前向星
int cnt,head[maxn];
struct Edge{int u,v,next;
}edge[maxn];
void add(int u,int v){edge[++cnt]=(Edge){u,v,head[u]}; head[u]=cnt;
}
vector<int> it[maxn];
int sta[maxn],ins[maxn],top,ls; //栈和是否入栈
void tarjan(int u){dfn[u]=low[u]=++tot;sta[top++]=u;ins[u]=1;for(int i=head[u];i;i=edge[i].next){int v=edge[i].v;if(dfn[v]==0){tarjan(v);low[u]=min(low[u],low[v]);}else if(ins[v]){low[u]=min(low[u],dfn[v]);}}int j=0;//已经构成环 if(dfn[u]==low[u]){ls++;while(1){j=sta[--top];ins[j]=0;it[ls].push_back(j);if(u==j) break;}}
}
int main(){scanf("%d",&n);int k;for(int i=1;i<=n;i++){scanf("%d",&k);add(i,k);}for(int i=1;i<=n;i++){if(dfn[i]==0) tarjan(i);}int ans=0x7fffffff;for(int i=1;i<=ls;i++){int x=it[i].size();if(x>1) ans=min(ans,x);}cout<<ans;return 0;
}
相关文章:
【图论】强连通分量
一.定义 强连通分量(Strongly Connected Components,简称SCC)是图论中的一个概念,用于描述有向图中的一组顶点,其中任意两个顶点之间都存在一条有向路径。换句话说,对于图中的任意两个顶点u和v,…...
网络:VRP介绍
1. VRP 华为使用的通用路由平台,华为的交换机、防火墙、安全设备、无线和路由器的命令行几乎一样。 2. VRP分为用户视图、系统视图。 3. 用户视图 user view <Huawei>:其中<>代表的是用户视图,Huawei是设备的名称。命令比较少。…...
iOS - 解压ipa包中的Assert.car文件
项目在 Archive 打包后,生成ipa包 将 xxx.ipa文件修改为zip后缀即 xxx.zip ,然后再双击解压,会生成一个 Payload 文件夹,里面一个文件 如下图: 然后显示改文件的包内容: 解压 Assets.car 文件的方式&…...
【Jmeter】配置不同业务请求比例,应对综合场景压测
目录 前言 Jmeter5.0新特性 核心改进 其他变化 资料获取方法 前言 Jmeter 5.0这次的核心改进是在许多地方改进了对 Rest 的支持,此外还有调试功能、录制功能的增强、报告的改进等。 我也是因为迁移到了Mac,准备在Mac上安装Jmeter的时候发现它已经…...
TCP拥塞控制详解 | 1. 概述
网络传输问题本质上是对网络资源的共享和复用问题,因此拥塞控制是网络工程领域的核心问题之一,并且随着互联网和数据中心流量的爆炸式增长,相关算法和机制出现了很多创新,本系列是免费电子书《TCP Congestion Control: A Systems …...
使用IPSEC VPN 在有防火墙的场景和有NAT转换的场景下实现隧道通信实验
目录 一、在有防火墙的场景 1、为所有设备配置对应ip地址: 2、进入两个防火墙实现公网互通 3、测试公网是否互通 4、进入SW1配置IPSEC VPN 5、进入SW2配置IPSEC VPN 6、配置策略方向ESP的流量 7、尝试使用PC1访问PC2 二、在有NAT地址转换的场景 1、为新增加…...
Go和Java实现适配器模式
Go和Java实现适配器模式 我们通过下面的实例来演示适配器模式的使用,其中,音频播放器设备只能播放 mp3 文件,通过使用一个更高级 的音频播放器来播放 vlc 和 mp4 文件。 1、适配器模式 适配器模式是作为两个不兼容的接口之间的桥梁。这种…...
接口相似数据结构复用率高?Apipost这招搞定!
在API设计和开发过程中,存在许多瓶颈,其中一个主要问题是在遇到相似数据结构的API时会产生重复性较多的工作:在每个API中都编写相同的数据,这不仅浪费时间和精力,还容易出错并降低API的可维护性。 为了解决这个问题&a…...
【零基础学Rust | 基础系列 | Hello, Rust】编写并运行第一个Rust程序
文章目录 前言一,创建项目二,两种编译方式1. 使用rustc编译器编译2. 使用Cargo编译 总结 前言 在开始学习任何一门新的编程语言时,都会从编写一个简单的 “Hello, World!” 程序开始。在这一章节中,将会介绍如何在Rust中编写并运…...
代理模式.
前言: 为什么要学习代理模式,因为AOP的底层机制就是动态代理! 代理模式: 静态代理 动态代理 静态代理 抽象角色 : 一般使用接口或者抽象类来实现 真实角色 : 被代理的角色 代理角色 : 代理真实角色 ; 代理真实角色后 , 一…...
BS框架说明
B/S架构 1.B/S框架,意思是前端(Browser 浏览器,小程序、app、自己写的)和服务器端(Server)组成的系统的框架结构 2.B/S框架,也可理解为web架构,包含前端、后端、数据库三大组成部分…...
iOS——Block签名
首先来看block结构体对象Block_layout(等同于clang编译出来的__Block_byref_a_0) #define BLOCK_DESCRIPTOR_1 1 struct Block_descriptor_1 {uintptr_t reserved;uintptr_t size; };#define BLOCK_DESCRIPTOR_2 1 struct Block_descriptor_2 {// requi…...
Flutter 图片选取及裁剪
在开发项目里修改用户头像的功能,涉及到图片选取及裁剪,基本实现步骤如下: 1、pubspec.yaml 添加 image_picker: ^1.0.1 image_cropper: ^4.0.1: dependencies:image_picker: ^1.0.1image_cropper: ^4.0.1flutter:sdk: flutter…...
C语言每日一题:11.《数据结构》链表分割。
题目一: 题目链接: 思路一:使用带头链表 1.构建两个新的带头链表,头节点不存储数据。 2.循环遍历原来的链表。 3.小于x的尾插到第一个链表。 4.大于等于x尾插到第二个链表。 5.进行链表合并,注意第二个链表的尾的下一…...
记一次Oracle归档日志异常增长问题的排查过程
Oracle归档日志是Oracle数据库的重要功能,用于将数据库的重做日志文件(Redo Log)保存到归档日志文件(Archive Log)中。归档日志的作用是提供数据库的备份和恢复功能,以及支持数据库的持续性和数据完整性。 …...
Java设计模式——类之间的关系
1.继承关系(泛化) 类与子类的关系,指一个类继承另外的一个类。 2.实现关系 一个类可以实现多个接口,实现所有接口的功能。 3.依赖关系 类B作为类A方法中的局部变量或者参数出现,表示A依赖B。 4.关联关系 类B作为类A中的成员变量出现&#…...
Dockerfile构建Redis镜像
建立工作目录 [rootlocalhost ~]# mkdir redis [rootlocalhost ~]# cd redis/ 编写Dockerfile文件 [rootlocalhost redis]# vim Dockerfile FROM centos:7 MAINTAINER dddd <dddd163.com> RUN yum -y install epel-release && yum -y install redis RUN sed -i …...
C高级DAY2
1.思维导图 2. 递归实现,输入一个数,输出这个数的每一位 递归实现,输入一个数,输出这个数的二进制c 写一个脚本,包含以下内容: 显示/etc/group文件中第五行的内容创建目录/home/ubuntu/copy切换工作路径到…...
Linux 服务管理
在Linux上,服务管理是指对系统中运行的服务进行启动、停止、重启、监控和配置的过程。以下是一些常用的Linux服务管理工具和命令: 1. systemctl:systemctl 是一个Linux系统服务管理工具,可以管理Systemd初始化系统的服务。常见的…...
问题记录 1 页面初始化触发el-form必填校验
bug: 先编辑table某条数据,然后关闭,再去新增的时候就会触发el-form必填校验, 网上搜了一下是因为 rules里触发的方式为change时,赋值数据的格式不一致导致触发校验, 最后也没找到正确的解决方法, 只能用很low方式去解决了 方案1. 把trigger改为 blur 失焦后触发 方案2. 初始化…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...
Python:操作 Excel 折叠
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...
什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...
html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...
[ACTF2020 新生赛]Include 1(php://filter伪协议)
题目 做法 启动靶机,点进去 点进去 查看URL,有 ?fileflag.php说明存在文件包含,原理是php://filter 协议 当它与包含函数结合时,php://filter流会被当作php文件执行。 用php://filter加编码,能让PHP把文件内容…...
