【图论】强连通分量进阶
一.作用
强连通分量可以判断环和进行缩点。还有一系列作用....
这篇文章介绍缩点
二.题目
https://www.luogu.com.cn/problem/P2341
三.思路
我们分析可以知道当一个点没有出度时,则为最受欢迎的牛。但如果有多个出度,则没有最受欢迎的牛。
这是只有一个出度的情况:

这是多个出度的情况:

但为什么要判断环&&对环缩点呢?

四.代码实现
只是微改,基础是
【图论】强连通分量_SY奇星的博客-CSDN博客
#include<bits/stdc++.h>
#define maxn 50005
using namespace std;
int n,m;
int head[maxn],cnt;
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 ls,l[maxn],out[maxn];//有多少环 ,这个数属于哪个环,点的出度
int dfn[maxn],low[maxn],tot;
int sta[maxn],ins[maxn],top;
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);l[j]=ls; //缩点, 即一个点属于哪个环,或者说是哪个缩点。 if(u==j) break;}}
}
int main(){scanf("%d%d",&n,&m);int u,v;for(int i=1;i<=m;i++){scanf("%d%d",&u,&v);add(u,v);}for(int i=1;i<=n;i++){if(dfn[i]==0) tarjan(i);}for(int i=1;i<=n;i++){for(int j=head[i];j;j=edge[j].next){int v=edge[j].v;if(l[i]!=l[v]){out[l[i]]++; //出度 }}}int ans=0;for(int i=1;i<=ls;i++){if(out[i]==0){if(ans==0) ans=i;else{cout<<0; return 0;} }}cout<<it[ans].size();return 0;
}
相关文章:
【图论】强连通分量进阶
一.作用 强连通分量可以判断环和进行缩点。还有一系列作用.... 这篇文章介绍缩点 二.题目 https://www.luogu.com.cn/problem/P2341 三.思路 我们分析可以知道当一个点没有出度时,则为最受欢迎的牛。但如果有多个出度,则没有最受欢迎的牛。 这是只有…...
perl GetOptions
在Perl中,你可以使用标准模块Getopt::Long来解析命令行选项(Command Line Options)。Getopt::Long模块允许你定义命令行选项以及它们的值,并且还可以处理各种类型的选项,如标志选项(flag options࿰…...
QGIS下载谷歌地图或者其他地图
QGIS安装Welcome to the QGIS project! 打开QGIS 添加图源 Google_Maps: https://mt1.google.com/vt/lyrsr&x{x}&y{y}&z{z} Google_Terrain: https://mt1.google.com/vt/lyrst&x{x}&y{y}&z{z} Google_Roads:https://mt1.google.com/vt/lyrsh&x{x…...
Python-re模块-正则表达式模块常用方法
re模块介绍: Python的re模块提供了正则表达式的功能,可以用来进行高级的字符串匹配和处理。re模块的主要功能包括: 编译正则表达式 - 使用re.compile()可以编译正则表达式字符串,生成正则表达式对象。 匹配字符串 - 使用正则表达式对象的match()、search()、finda…...
修改el-select或者el-input样式失效
下午改el-input和el-select这两个的样式真的烦,,,还不如写原生标签了。。 样式使用的是sass 我已经在样式器中挨着挨着去找了,把层级的类都写下来了 .select-wraper{//下拉框.el-select{.el-input .el-input__wrapper{backgrou…...
【Apifox】Apifox设置参数说明:
文章目录 一、效果:二、Query参数:三、返回响应: 一、效果: 二、Query参数: 三、返回响应:...
离线数仓中,为什么用两个flume,一个kafka
实时数仓中,为什么没有零点漂移问题? 因为flink直接取的事件时间用kafka是为了速度快,并且数据不丢,那为什么既用了kafkachannel,也用了kafka,而不只用kafkachannel呢? 因为需要削峰填谷离线数仓…...
p7付费课程笔记6:CMS GC
目录 前言 工作步骤 缺点 问题 前言 上一章节我们讲了串/并行GC,这一章节说下CMS GC。看前思考一个问题,并行GC与CMS GC的区别在哪里。 什么是CMS收集器 CMS(Concurrent Mark-Sweep)是以牺牲吞吐量为代价来获得最短回收停顿时间的垃圾回收器。对于…...
Linux性能分析--cpuinfo的内核实现
目录 一、引言 二、Linux性能分析工具介绍 ------>2.1、proc ------------>2.1.1、内核中的proc文件系统 ------------>2.2.2、proc的实现 ------>2.2、cpuinfo ------------>2.2.1、cpuinfo的内核实现 ------------>2.2.2、寄存器获取cpuinfo数据 …...
鲁大师7月新机性能/流畅/久用榜:骁龙8 Gen2领先版亮相,性能跑分再破新高
摘要:iQOO 11S突破上限,红魔8S Pro再创新高 继五月六月,搭载天玑9200的机型相继迎来上市之后,高通也终于按耐不住。 本月所有上市的新机均搭载高通骁龙系列芯片,其中骁龙8 Gen2领先版迎来首次亮相,除了主打…...
【QT学习】01:helloqt
helloqt OVERVIEW helloqt一、helloqt1.使用向导创建2.手动创建3.pro文件4.Qt应用程序框架 二、按钮创建main.cppmywidget.cpp 三、对象模型1.对象树引入2.存在的问题 一、helloqt 创建一个qt项目,可以使用creator的向导创建,也可自己手动创建ÿ…...
学习gRPC (三)
测试gRPC例子 编写proto文件实现服务端代码实现客户端代码 通过gRPC 已经编译并且安装好之后,就可以在源码目录下找到example 文件夹下来试用gRPC 提供的例子。 在这里我使用VS2022来打开仓库目录下example/cpp/helloworld目录 编写proto文件 下面是我改写的exa…...
【html】学习记录
1.在建立一个页面的时候不是打开软件就开始写代码,要先规划好页面的布局框架,不然思想会很混乱,如做个人简历,要分区分块,把每个区域的内容搞清楚。 2.html的很多标签看上去作用都是一样的,但是实际有很大不…...
2023年人工智能技术与智慧城市发展白皮书
人工智能与智慧城市是当前热门的话题和概念,通过将人工智能技术应用在城市管理和服务中,利用自动化、智能化和数据化的方式提高城市运行效率和人民生活质量,最终实现城市发展的智慧化,提升城市居民的幸福感。 AI技术在城市中的应…...
《Python入门到精通》条件控制 if 语句
「作者主页」:士别三日wyx 「作者简介」:CSDN top100、阿里云博客专家、华为云享专家、网络安全领域优质创作者 「推荐专栏」:小白零基础《Python入门到精通》 if 语句 1、四种语法格式1.1、if1.2、if else1.3、if elif else1.4、if 嵌套 2、…...
如何编写一个易于维护的考试系统源码
编写一个易于维护的考试系统源码对于开发人员来说非常重要。一个易于维护的系统可以使代码更易于理解、修改和扩展,从而提高开发效率和系统稳定性。 第一步:良好的项目结构 良好的项目结构是一个易于维护的源码的基础。可以按照模块、功能或层次等方式…...
day 2 |977.有序数组的平方、209.长度最小的子数组、59.螺旋矩阵II
目录: 解题及思路学习 977.有序数组的平方 https://leetcode.cn/problems/squares-of-a-sorted-array/submissions/ 给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。 示例 1&a…...
【力扣每日一题】2023.8.2 翻转卡片游戏
目录 题目: 示例: 分析: 代码: 题目: 示例: 分析: 这道题不是什么翻转卡片游戏,这就是纯纯的文字游戏,要是能看懂题目那就是非常简单,接下来我就给大家分…...
IDEA设置中文 中文插件
IDEA设置中文 中文插件 首先进入idea File --> Setting --> Plugin 输入Chinese 搜索插件 选择下图插件进行install 安装完成后,重启idea即可...
Python——调用webdriver.Chrome() 报错
今天运行脚本,报错内容如下: collecting ... login_case.py:None (login_case.py) login_case.py:11: in <module> dr webdriver.Chrome() D:\Program Files (x86)\Python\Python39\Lib\site-packages\selenium\webdriver\chrome\webdriver.p…...
【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
自然语言处理——循环神经网络
自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元(GRU)长短期记忆神经网络(LSTM)…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式
今天是关于AI如何在教学中增强学生的学习体验,我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育,这并非炒作,而是已经发生的巨大变革。教育机构和教育者不能忽视它,试图简单地禁止学生使…...
腾讯云V3签名
想要接入腾讯云的Api,必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口,但总是卡在签名这一步,最后放弃选择SDK,这次终于自己代码实现。 可能腾讯云翻新了接口文档,现在阅读起来,清晰了很多&…...
tauri项目,如何在rust端读取电脑环境变量
如果想在前端通过调用来获取环境变量的值,可以通过标准的依赖: std::env::var(name).ok() 想在前端通过调用来获取,可以写一个command函数: #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...
【深度学习新浪潮】什么是credit assignment problem?
Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...
