【图论】强连通分量

一.定义

 强连通分量(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;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

数学学习——最优化问题引入、凸集、凸函数、凸优化、梯度、Jacobi矩阵、Hessian矩阵

文章目录 最优化问题引入凸集凸函数凸优化梯度Jacobi矩阵Hessian矩阵 最优化问题引入 例如&#xff1a;有一根绳子&#xff0c;长度一定的情况下&#xff0c;需要如何围成一个面积最大的图像&#xff1f;这就是一个最优化的问题。就是我们高中数学中最常见的最值问题。 最优化…

《Java-SE-第二十七章》之常见的锁策略

前言 在你立足处深挖下去,就会有泉水涌出!别管蒙昧者们叫嚷:“下边永远是地狱!” 博客主页&#xff1a;KC老衲爱尼姑的博客主页 博主的github&#xff0c;平常所写代码皆在于此 共勉&#xff1a;talk is cheap, show me the code 作者是爪哇岛的新手&#xff0c;水平很有限&…

Maven发布项目到Nexus私服

项目pom配置 在项目pom.xml中文件中的仓库配置&#xff0c;Nexus私服如何搭建在这里不介绍了可自行百度。 <distributionManagement><repository><id>releases</id><name>Nexus Release Repository</name><url>http://私服地址:34…

hive删除数据进行恢复

在实际开发或生产中&#xff0c;hive表如果被误删&#xff0c;如被truncate或是分区表的分区被误删了&#xff0c;只要在回收站的清空周期内&#xff0c;是可以恢复数据的&#xff0c;步骤如下&#xff1a; &#xff08;1&#xff09; 先找到被删除数据的存放目录&#xff0c;…

Linux NUMA架构(非统一内存访问)

NUMA架构 NUMA Architecture| Non Uniform Memory Access Policy/Model | Numa Node Configuration (CPU Affinity) NUMA架构产生的原因 cpu的高速处理功能和内存存储直接的速度会严重影响cpu的性能。传统的计算机单核架构,cpu通过内存总线(内存访问控制器)直接连接到一…

在CSDN学Golang云原生(Kubernetes声明式资源管理Kustomize)

一&#xff0c;生成资源 在 Kubernetes 中&#xff0c;我们可以通过 YAML 或 JSON 文件来定义和创建各种资源对象&#xff0c;例如 Pod、Service、Deployment 等。下面是一个简单的 YAML 文件示例&#xff0c;用于创建一个 Nginx Pod&#xff1a; apiVersion: v1 kind: Pod m…

使用Express部署Vue项目

使用Express部署Vue项目 目录 1. 背景 2. 配置Vue CLI 1.1 安装nodejs 1.2 创建vue-cli 1.3 创建vue项目 1.4 构建vue项目3. 配置Express 2.1 安装express 2.2 创建项目4. 使用express部署vue项目 1&#xff0c;背景 我们想要做一个前后端分离的课程项目&#xff0c;前端…

推荐两款github敏感信息搜集工具(gsil、gshark)

推荐两款github敏感信息搜集工具&#xff08;gsil、gshark&#xff09; - 云社区 - 腾讯云 (tencent.com) github敏感信息泄露是很多企业时常忽视的一个问题&#xff0c;国外有一份研究报告显示&#xff0c;在超过24,000份的GitHub公开数据中&#xff0c;发现有数千个文件中可能…

学习笔记——压力测试案例,监控平台

测试案例 # 最简单的部署方式直接单机启动 nohup java -jar lesson-one-0.0.1-SNAPSHOT.jar > ./server.log 2>&1 &然后配置执行计划&#xff1a; 新建一个执行计划 配置请求路径 配置断言配置响应持续时间断言 然后配置一些查看结果的统计报表或者图形 然后我…

数据中台系列2:rabbitMQ 安装使用之 window 篇

RabbitMQ 是一个开源的消息队列系统&#xff0c;是高级消息队列协议&#xff08;AMQP&#xff09;的标准实现&#xff0c;用 erlang 语言开发。 因此安装 RabbitMQ 之前要先安装好 erlang。 1、安装 erlang 到 这里 下载本机能运行的最新版 erlang 安装包。如果本机没有装过 …

双重for循环优化

项目中有段代码逻辑是个双重for循环&#xff0c;发现数据量大的时候&#xff0c;直接导致数据接口响应超时&#xff0c;这里记录下不断优化的过程&#xff0c;算是抛砖引玉吧~ Talk is cheap,show me your code&#xff01; 双重for循环优化 1、数据准备2、原始双重for循环3、…

Atcoder 做题记录

My OI Blog A R C 155 F \mathbb{ARC \ 155 \ F} ARC 155 F E, F 先咕着&#xff0c;做一些多项式题&#xff0c;这篇题解是我人工翻译的 [1] Double Counting 双重计数 考虑从叶子节点开始&#xff0c;用唯一的方式&#xff08;如果有的话&#xff09;来构造出一棵满足条件的树…

许战海咨询方法论系列白皮书在京隆重发布

新时代&#xff0c;面对剧烈变化的竞争环境&#xff0c;企业如何实现结构性增长&#xff1f; 7月31日&#xff0c;许战海咨询最新研究成果——《主品牌进化战略》、《第二招牌增长战略》、《链主品牌&#xff1a;制造业的竞争之王》三本核心方法论白皮书&#xff0c;重磅发布。…

稍微深度踩坑haystack + whoosh + jieba

说到django的全文检索&#xff0c;网上基本推荐的都是 haystack whoosh jieba 的方案。 由于我的需求对搜索时间敏感度较低&#xff0c;但是要求不能有数据的错漏。 但是没有调试的情况下&#xff0c;搜索质量真的很差&#xff0c;搞得我都想直接用Like搜索数据库算了。 但是…

C++设计模式之过滤器设计模式

C过滤器设计模式 什么是过滤器设计模式 过滤器设计模式是一种行为型设计模式&#xff0c;它允许你在特定的条件下对输入或输出进行过滤&#xff0c;以便实现不同的功能。 该模式有什么优缺点 优点 可扩展性&#xff1a;过滤器设计模式允许您轻松地添加、删除或替换过滤器&a…

CVPR2023新作:源数据集对迁移学习性能的影响以及相应的解决方案

Title: A Data-Based Perspective on Transfer Learning (迁移学习的基于数据的观点) Affiliation: MIT (麻省理工学院) Authors: Saachi Jain, Hadi Salman, Alaa Khaddaj, Eric Wong, Sung Min Park, Aleksander Mądry Keywords: transfer learning, source dataset, dow…

iOS 应用上架的步骤和工具简介

APP开发助手是一款能够辅助iOS APP上架到App Store的工具&#xff0c;它解决了iOS APP上架流程繁琐且耗时的问题&#xff0c;帮助跨平台APP开发者顺利将应用上架到苹果应用商店。最重要的是&#xff0c;即使没有配置Mac苹果机&#xff0c;也可以使用该工具完成一系列操作&#…

算法39:Excel 表列序号

一、需求 给你一个字符串 columnTitle &#xff0c;表示 Excel 表格中的列名称。返回 该列名称对应的列序号 。 例如&#xff1a; A -> 1 B -> 2 C -> 3 … Z -> 26 AA -> 27 AB -> 28 … 示例 1&#xff1a; 输入: columnTitle “A” 输出: 1 示例 2&…

Minio在windows环境配置https访问

minio启动后&#xff0c;默认访问方式为http&#xff0c;但是有的时候我们的访问场景必须是https&#xff0c;浏览器有的会默认以https进行访问&#xff0c;这个时候就需要我们进行配置上的调整&#xff0c;将minio从http访问升级到https。而查看minio的官方文档&#xff0c;并…

配置IPv6 over IPv4手动隧道示例

组网需求 如图1所示&#xff0c;两台IPv6主机分别通过SwitchA和SwitchC与IPv4骨干网络连接&#xff0c;客户希望两台IPv6主机能通过IPv4骨干网互通。 图1 配置IPv6 over IPv4手动隧道组网图 配置思路 配置IPv6 over IPv4手动隧道的思路如下&#xff1a; 配置IPv4网络。配置接…