给定n个结点m条边的简单无向图,判断该图是否存在鱼形状的子图:有一个环,其中有一个结点有另外两条边,连向不在环内的两个结点。若有,输出子图的连边
题目
思路:

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define fi first
#define se second
#define lson p << 1
#define rson p << 1 | 1
const int maxn = 1e6 + 5, inf = 1e18 * 3, maxm = 4e4 + 5, mod = 1e9 + 7;
int a[maxn], b[maxn];
int n, m;
string s;
bool vis[maxn];
vector<int> G[maxn];
int from, to;
vector<int> tmp, vec;
int deg[maxn];void dfs(int u, int p){if(u == to && p == from) return;if(vis[u]) return;vis[u] = 1;tmp.pb(u);if(u == to){vec = tmp;return;}for(auto v : G[u]){dfs(v, u);}tmp.pop_back();
}
void solve(){int res = 0;int k, x, q;cin >> n >> m;for(int i = 1; i <= n; i++){G[i].clear();deg[i] = 0;}for(int i = 1; i <= m; i++){int u, v;cin >> u >> v;G[u].pb(v);G[v].pb(u);deg[u]++;deg[v]++;}for(int u = 1; u <= n; u++){if(deg[u] < 4) continue;for(auto v : G[u]){for(int i = 1; i <= n; i++){vis[i] = 0;}from = u;to = v;vec.clear();tmp.clear();dfs(u, u);if(vec.empty()) continue;vector<int> extra;tmp.clear();for(auto x : G[u]){if(x == vec.back() || x == *(vec.begin() + 1)) continue;if(find(vec.begin(), vec.end(), x) == vec.end()){//不在环内extra.pb(x);if(extra.size() == 2) break;}else{tmp.pb(x);//在环内,且与u相连}}vector<int> vt;if(extra.size() < 2){for(auto x : vec){vt.pb(x);if(find(tmp.begin(), tmp.end(), x) != tmp.end()){//在tmp内break;}}extra.pb(vec.back());for(int i = vec.size() - 1; i >= 0; i--){int x = vec[i];if(find(tmp.begin(), tmp.end(), x) != tmp.end()){extra.pb(x);break;}}// extra.pb(vec.end() - 2) 不能这样写,因为这个结点不一定与u相连// extra.pb(tmp.back()); 不能这样写,因为tmp的顺序跟环的结点顺序不一致extra.resize(2);vec = vt;}cout << "Yes\n";cout << vec.size() + 2 << '\n';int m = vec.size();for(int i = 0; i < vec.size(); i++){cout << vec[i] << ' ' << vec[(i + 1) % m] << '\n';}cout << u << ' ' << extra[0] << '\n';cout << u << ' ' << extra[1] << '\n';return;}}cout << "No\n";
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int T = 1;cin >> T;while (T--){solve();}return 0;
}
相关文章:
给定n个结点m条边的简单无向图,判断该图是否存在鱼形状的子图:有一个环,其中有一个结点有另外两条边,连向不在环内的两个结点。若有,输出子图的连边
题目 思路: #include <bits/stdc.h> using namespace std; #define int long long #define pb push_back #define fi first #define se second #define lson p << 1 #define rson p << 1 | 1 const int maxn 1e6 5, inf 1e18 * 3, maxm 4e4 …...
深入理解lambda表达式
深入理解ASP.NET Core中的中间件和Lambda表达式 var builder WebApplication.CreateBuilder(args); var app builder.Build(); app.Use(async (context, next) > { // Add code before request. await next(context);// Add code after request.}); 这段C#代码是用于设…...
删除 Windows 设备和驱动器中的 WPS网盘、百度网盘等快捷图标
在安装诸如WPS软件、百度云盘、爱奇艺等客户端后,Windows 的“我的电脑”(或“此电脑”)中的“设备和驱动器”部分会出现对应的软件图标。这种情况被许多技术人员视为不必要的干扰,因此许多用户想要知道如何隐藏或删除这些图标。 …...
【深度学习:DICOM 注释工具】在 DICOM 注释工具中寻找的 7 个功能
【深度学习:DICOM 注释工具】在 DICOM 注释工具中寻找的 7 个功能 原生 DICOM 支持原生 3D 注释易于使用的界面DICOM 图像的自动注释质量控制功能审计跟踪SOC2 和 HIPAA 合规性 如果您尝试为医疗 AI 模型创建训练数据,您可能已经使用了免费的开源工具&am…...
Spring Boot与Kafka集成教程
当然可以,这里为您提供一个简化版的Spring Boot与Kafka集成教程: 新建Spring Boot项目 使用Spring Initializr或您喜欢的IDE(如IntelliJ IDEA, Eclipse等)新建一个Spring Boot项目。 添加依赖 在项目的pom.xml文件中,…...
基于飞腾ARM+FPGA国产化计算模块联合解决方案
联合解决方案概述 随着特殊领域电子信息系统对自主创新需求的日益提升,需不断开展国产抗恶劣环境计算整机及模块产 品的研制和升级。特殊领域电子信息系统的自主创新,是指依靠自身技术手段和安全机制,实现信息系统从硬 件到软件的自主研发…...
关于DVWA靶场Could not connect to the database service的几种解决办法
总的来说这个问题都是 config 配置文件没有修改正确 一般修改数据库的用户名和密码与 phpstudy 一致并且添加了 key 就能初始化成功的 但是我还遇到过另一种情况,修改了上面的东西依旧无法连接到数据库 Could not connect to the database service. Please check …...
已解决ModuleNotFoundError: No module named ‘paddle‘异常的正确解决方法,亲测有效!!!
已解决ModuleNotFoundError: No module named paddle异常的正确解决方法,亲测有效!!! 文章目录 问题分析 报错原因 解决思路 解决方法 总结 在人工智能和深度学习领域,PaddlePaddle是由百度发起的开源平台&#…...
并发编程之深入理解JVM并发三大特性
并发编程之深入理解JVM&并发三大特性 并发编程解决的问题 多线程同步(一个线程需要等待另一个线程的结果,一个线程依赖于另一个线程),互斥(一个资源只能一个线程使用),分工(…...
helm部署gitlab-runner问题解决
关于.gitlab-ci.yml中build镜像时,docker守护进程未启动错误 问题截图 解决方法 conf.toml添加 [[runners.kubernetes.volumes.host_path]]name "docker"mount_path "/var/run/docker.sock"read_only falsehost_path "/var/run/dock…...
[嵌入式系统-28]:开源的虚拟机监视器和仿真器:QEMU(Quick EMUlator)与VirtualBox、VMware Workstation的比较
目录 一、QEMU概述 1.1 QEMU架构 1.2 QEMU概述 1.3 什么时候需要QEMU 1.4 QEMU两种操作模式 1.5 QEMU模拟多种CPU架构 二、QEMU与其他虚拟机的比较 2.1 常见的虚拟化技术 2.1 Linux KVM 2.2 Windows VirtualBox 2.3 Windows VMware workstation 三、VirtualBox、VM…...
计算机组成原理:存储系统【三】
🌈个人主页:godspeed_lucip 🔥 系列专栏:计算机组成与原理基础 🚀1 只读存储器ROM✈️1.1 总览✈️1.2 各种ROM✈️1.3 计算机内部重要的ROM✈️1.4 总结 🚀2 主存储器与CPU的连接🛩️2.1 总览&…...
学习Android的第十三天
目录 Android TextClock 文本时钟控件 TextClock 控件主要属性和方法 简单的 TextClock 参考文档 Android AnalogClock 控件 AnalogClock 属性 Android Chronometer 计时器 Chronometer 属性 Chronometer 主要方法 范例: 完整的计时器 范例: …...
【开源】SpringBoot框架开发学校热点新闻推送系统
目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 新闻类型模块2.2 新闻档案模块2.3 新闻留言模块2.4 新闻评论模块2.5 新闻收藏模块 三、系统设计3.1 用例设计3.2 数据库设计3.2.1 新闻类型表3.2.2 新闻表3.2.3 新闻留言表3.2.4 新闻评论表3.2.5 新闻收藏表 四、系统展…...
代码随想录刷题笔记 DAY 28 | 复原 IP 地址 No.93 | 子集 No.78 | 子集 II No.90
文章目录 Day 2801. 复原 IP 地址(No. 93)1.1 题目1.2 笔记1.3 代码 02. 子集(No. 78)2.1 题目2.2 笔记2.3 代码 03. 子集 II(No. 90)3.1 题目3.2 笔记3.3 代码 Day 28 01. 复原 IP 地址(No. 9…...
LeetCode LCR 085. 括号生成
题目链接https://leetcode.cn/problems/IDBivT/description/ 正整数 n 代表生成括号的对数,请设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。 class Solution {public List<String> generateParenthesis(int n) {List<String>…...
django定时任务(django-crontab)
目录 一:安装django-crontab: 二:添加django_crontab到你的INSTALLED_APPS设置: 三:运行crontab命令来创建或更新cron作业: 四:定义你的cron作业 五:创建你的管理命令ÿ…...
【教3妹学编程-算法题】输入单词需要的最少按键次数 II
2哥 : 叮铃铃,3妹,准备复工了啊,过年干嘛呢,是不是逛吃逛吃,有没有长胖呢。 3妹:切,不想上班,假期能不能重来一遍啊,虽然在家我妈张罗着要给我相亲呢。可是在家还是很好的…...
突破编程_C++_高级教程(多线程编程实例)
1 生产者-消费者模型 生产者-消费者模型是一种多线程协作的设计模式,它主要用于处理生产数据和消费数据的过程。在这个模型中,存在两类线程:生产者线程和消费者线程。生产者线程负责生产数据,并将其放入一个共享的数据缓冲区&…...
精读《Function Component 入门》
1. 引言 如果你在使用 React 16,可以尝试 Function Component 风格,享受更大的灵活性。但在尝试之前,最好先阅读本文,对 Function Component 的思维模式有一个初步认识,防止因思维模式不同步造成的困扰。 2. 精读 什…...
STM8/STM32 GPIO触摸按键实现与优化
基于STM8/STM32的GPIO触摸按键实现技术解析1. 触摸按键技术概述1.1 传统方案与MCU实现对比在消费类电子产品中,触摸按键的实现通常有两种主流方案:专用触摸IC方案:集成度高但成本较高MCU GPIO方案:利用通用微控制器实现࿰…...
从零搭建WebRTC信令服务:SpringBoot WebSocket与Vue3的实战协同
1. WebRTC信令服务基础认知 第一次接触WebRTC时,我被它直接建立P2P连接的能力惊艳到了——就像两个陌生人突然跳过所有中间环节直接开始面对面交流。但很快我发现,这种"魔法"背后需要一套精密的协调机制,这就是信令服务的用武之地。…...
如何实现微信聊天记录的终极掌控:WeChatMsg完全指南
如何实现微信聊天记录的终极掌控:WeChatMsg完全指南 【免费下载链接】WeChatMsg 提取微信聊天记录,将其导出成HTML、Word、CSV文档永久保存,对聊天记录进行分析生成年度聊天报告 项目地址: https://gitcode.com/GitHub_Trending/we/WeChatM…...
告别模拟音频线!用MAX98357A数字功放芯片,5分钟搞定I2S直连ESP32播放MP3
5分钟实现ESP32数字音频播放:MAX98357A功放芯片极简开发指南 在智能硬件开发中,音频输出功能常被视为"必要但麻烦"的组件——传统方案需要DAC转换、运放电路、滤波网络等一系列复杂设计。而MAX98357A这颗仅指甲盖大小的芯片,用纯数…...
国密SM4算法在Web与Java应用中的跨平台加解密实战
1. 国密SM4算法简介与应用场景 国密SM4算法是我国自主设计的分组对称加密算法,于2012年成为国家密码行业标准(GM/T 0002-2012)。作为替换国际算法(如AES)的重要选择,SM4在金融、政务、物联网等领域得到广泛…...
MIKE21不同下垫面添加随时空变化净雨过程线
近期很多文章都是关于市政管网方向的,今天小编换个口味,对MIKE21中添加降雨边界文件有了一种新的制作形式。其实这种方法涉及到MIKE SHE一个小工具,不过确实很实用,就让小编给大家介绍下吧。第一步 下垫面转DFS2熟悉MIKE21的同学们…...
别再拍脑袋定A/B测试样本量了!用Python/Excel/R三分钟算出靠谱结果
别再拍脑袋定A/B测试样本量了!用Python/Excel/R三分钟算出靠谱结果 每次启动A/B测试前,团队总会陷入同样的争论:"这次实验需要多少流量才够?"产品经理凭经验说"10万用户应该够了",运营同学翻出上次…...
bge-large-zh-v1.5在RAG中的应用:提升问答系统准确率
bge-large-zh-v1.5在RAG中的应用:提升问答系统准确率 1. RAG系统与Embedding模型的关系 1.1 什么是RAG系统 RAG(Retrieval-Augmented Generation)系统是现代问答系统的核心技术架构,它通过两个关键步骤回答用户问题:…...
【Cuvil编译器生产级AI推理落地指南】:20年编译器老兵亲授Python模型从PyTorch到裸金属推理的7大避坑红线
第一章:Cuvil编译器在Python AI推理中的应用Cuvil 是一款面向AI工作负载的轻量级领域专用编译器,专为优化Python生态中基于NumPy、Torch和ONNX的推理流程而设计。它不依赖传统JIT或解释器层,而是通过静态图提取、张量算子融合与硬件感知调度&…...
FreeRTOS系统时钟节拍配置指南:从1ms到100ms如何选择最优心跳频率(含STM32F4实测数据)
FreeRTOS系统时钟节拍配置实战:从理论到STM32F4调优全解析 在嵌入式实时操作系统领域,系统时钟节拍如同人体心跳般重要——它决定了系统处理延时、超时等时间相关事件的精度与效率。对于使用FreeRTOS的开发者而言,时钟节拍频率的选择绝非简单…...
