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

【图论】强连通分量

一.定义

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

相关文章:

【图论】强连通分量

一.定义 强连通分量&#xff08;Strongly Connected Components&#xff0c;简称SCC&#xff09;是图论中的一个概念&#xff0c;用于描述有向图中的一组顶点&#xff0c;其中任意两个顶点之间都存在一条有向路径。换句话说&#xff0c;对于图中的任意两个顶点u和v&#xff0c;…...

网络:VRP介绍

1. VRP 华为使用的通用路由平台&#xff0c;华为的交换机、防火墙、安全设备、无线和路由器的命令行几乎一样。 2. VRP分为用户视图、系统视图。 3. 用户视图 user view <Huawei>&#xff1a;其中<>代表的是用户视图&#xff0c;Huawei是设备的名称。命令比较少。…...

iOS - 解压ipa包中的Assert.car文件

项目在 Archive 打包后&#xff0c;生成ipa包 将 xxx.ipa文件修改为zip后缀即 xxx.zip &#xff0c;然后再双击解压&#xff0c;会生成一个 Payload 文件夹&#xff0c;里面一个文件 如下图&#xff1a; 然后显示改文件的包内容&#xff1a; 解压 Assets.car 文件的方式&…...

【Jmeter】配置不同业务请求比例,应对综合场景压测

目录 前言 Jmeter5.0新特性 核心改进 其他变化 资料获取方法 前言 Jmeter 5.0这次的核心改进是在许多地方改进了对 Rest 的支持&#xff0c;此外还有调试功能、录制功能的增强、报告的改进等。 我也是因为迁移到了Mac&#xff0c;准备在Mac上安装Jmeter的时候发现它已经…...

TCP拥塞控制详解 | 1. 概述

网络传输问题本质上是对网络资源的共享和复用问题&#xff0c;因此拥塞控制是网络工程领域的核心问题之一&#xff0c;并且随着互联网和数据中心流量的爆炸式增长&#xff0c;相关算法和机制出现了很多创新&#xff0c;本系列是免费电子书《TCP Congestion Control: A Systems …...

使用IPSEC VPN 在有防火墙的场景和有NAT转换的场景下实现隧道通信实验

目录 一、在有防火墙的场景 1、为所有设备配置对应ip地址&#xff1a; 2、进入两个防火墙实现公网互通 3、测试公网是否互通 4、进入SW1配置IPSEC VPN 5、进入SW2配置IPSEC VPN 6、配置策略方向ESP的流量 7、尝试使用PC1访问PC2 二、在有NAT地址转换的场景 1、为新增加…...

Go和Java实现适配器模式

Go和Java实现适配器模式 我们通过下面的实例来演示适配器模式的使用&#xff0c;其中&#xff0c;音频播放器设备只能播放 mp3 文件&#xff0c;通过使用一个更高级 的音频播放器来播放 vlc 和 mp4 文件。 1、适配器模式 适配器模式是作为两个不兼容的接口之间的桥梁。这种…...

接口相似数据结构复用率高?Apipost这招搞定!

在API设计和开发过程中&#xff0c;存在许多瓶颈&#xff0c;其中一个主要问题是在遇到相似数据结构的API时会产生重复性较多的工作&#xff1a;在每个API中都编写相同的数据&#xff0c;这不仅浪费时间和精力&#xff0c;还容易出错并降低API的可维护性。 为了解决这个问题&a…...

【零基础学Rust | 基础系列 | Hello, Rust】编写并运行第一个Rust程序

文章目录 前言一&#xff0c;创建项目二&#xff0c;两种编译方式1. 使用rustc编译器编译2. 使用Cargo编译 总结 前言 在开始学习任何一门新的编程语言时&#xff0c;都会从编写一个简单的 “Hello, World!” 程序开始。在这一章节中&#xff0c;将会介绍如何在Rust中编写并运…...

代理模式.

前言&#xff1a; 为什么要学习代理模式&#xff0c;因为AOP的底层机制就是动态代理&#xff01; 代理模式&#xff1a; 静态代理 动态代理 静态代理 抽象角色 : 一般使用接口或者抽象类来实现 真实角色 : 被代理的角色 代理角色 : 代理真实角色 ; 代理真实角色后 , 一…...

BS框架说明

B/S架构 1.B/S框架&#xff0c;意思是前端&#xff08;Browser 浏览器&#xff0c;小程序、app、自己写的&#xff09;和服务器端&#xff08;Server&#xff09;组成的系统的框架结构 2.B/S框架&#xff0c;也可理解为web架构&#xff0c;包含前端、后端、数据库三大组成部分…...

iOS——Block签名

首先来看block结构体对象Block_layout&#xff08;等同于clang编译出来的__Block_byref_a_0&#xff09; #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 图片选取及裁剪

在开发项目里修改用户头像的功能&#xff0c;涉及到图片选取及裁剪&#xff0c;基本实现步骤如下&#xff1a; 1、pubspec.yaml 添加 image_picker: ^1.0.1 image_cropper: ^4.0.1&#xff1a; dependencies:image_picker: ^1.0.1image_cropper: ^4.0.1flutter:sdk: flutter…...

C语言每日一题:11.《数据结构》链表分割。

题目一&#xff1a; 题目链接&#xff1a; 思路一&#xff1a;使用带头链表 1.构建两个新的带头链表&#xff0c;头节点不存储数据。 2.循环遍历原来的链表。 3.小于x的尾插到第一个链表。 4.大于等于x尾插到第二个链表。 5.进行链表合并&#xff0c;注意第二个链表的尾的下一…...

记一次Oracle归档日志异常增长问题的排查过程

Oracle归档日志是Oracle数据库的重要功能&#xff0c;用于将数据库的重做日志文件&#xff08;Redo Log&#xff09;保存到归档日志文件&#xff08;Archive Log&#xff09;中。归档日志的作用是提供数据库的备份和恢复功能&#xff0c;以及支持数据库的持续性和数据完整性。 …...

Java设计模式——类之间的关系

1.继承关系(泛化) 类与子类的关系&#xff0c;指一个类继承另外的一个类。 2.实现关系 一个类可以实现多个接口&#xff0c;实现所有接口的功能。 3.依赖关系 类B作为类A方法中的局部变量或者参数出现&#xff0c;表示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. 递归实现&#xff0c;输入一个数&#xff0c;输出这个数的每一位 递归实现&#xff0c;输入一个数&#xff0c;输出这个数的二进制c 写一个脚本&#xff0c;包含以下内容&#xff1a; 显示/etc/group文件中第五行的内容创建目录/home/ubuntu/copy切换工作路径到…...

Linux 服务管理

在Linux上&#xff0c;服务管理是指对系统中运行的服务进行启动、停止、重启、监控和配置的过程。以下是一些常用的Linux服务管理工具和命令&#xff1a; 1. systemctl&#xff1a;systemctl 是一个Linux系统服务管理工具&#xff0c;可以管理Systemd初始化系统的服务。常见的…...

问题记录 1 页面初始化触发el-form必填校验

bug: 先编辑table某条数据,然后关闭,再去新增的时候就会触发el-form必填校验, 网上搜了一下是因为 rules里触发的方式为change时,赋值数据的格式不一致导致触发校验, 最后也没找到正确的解决方法, 只能用很low方式去解决了 方案1. 把trigger改为 blur 失焦后触发 方案2. 初始化…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

从物理机到云原生:全面解析计算虚拟化技术的演进与应用

前言&#xff1a;我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM&#xff08;Java Virtual Machine&#xff09;让"一次编写&#xff0c;到处运行"成为可能。这个软件层面的虚拟化让我着迷&#xff0c;但直到后来接触VMware和Doc…...

五子棋测试用例

一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏&#xff0c;有着深厚的文化底蕴。通过将五子棋制作成网页游戏&#xff0c;可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家&#xff0c;都可以通过网页五子棋感受到东方棋类…...