给定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. 精读 什…...
工业相机丢帧问题全解析:从硬件到软件的5个实战解决方案
工业相机丢帧问题全解析:从硬件到软件的5个实战解决方案 在机器视觉系统的实际应用中,工业相机丢帧问题就像一条潜伏的生产线杀手——它可能悄无声息地导致检测漏判、定位偏差甚至整批产品质检失效。去年某汽车零部件厂商就曾因2%的随机丢帧,…...
如何快速掌握Monaco Editor代码模板变量默认值导入的完整指南
如何快速掌握Monaco Editor代码模板变量默认值导入的完整指南 【免费下载链接】monaco-editor A browser based code editor 项目地址: https://gitcode.com/gh_mirrors/mo/monaco-editor 想要在Web应用中实现像VS Code一样强大的代码编辑器体验吗?Monaco Ed…...
打造直播APP礼物列表丝滑体验:SmartRefreshLayout实战指南
打造直播APP礼物列表丝滑体验:SmartRefreshLayout实战指南 【免费下载链接】SmartRefreshLayout 🔥下拉刷新、上拉加载、二级刷新、淘宝二楼、RefreshLayout、OverScroll,Android智能下拉刷新框架,支持越界回弹、越界拖动…...
2026年企业AI HR选型实用手册
导读:这份2026年企业AI HR选型实用手册由eRoad易路出品,核心围绕AI技术与人力资源管理的深度融合,提出以“搭子”方法论打造企业落地AI HR的最短路径,展现了从技术应用到产业落地的HR智能化进化方向。关注公众号:【互联…...
解决VSCode远程连接卡在‘Waiting for server log...‘的兼容性问题
1. 问题现象与初步排查 最近在给客户部署远程开发环境时,遇到了一个典型问题:使用VSCode通过SSH连接CentOS 7服务器时,界面一直卡在"Waiting for server log..."状态。这个现象特别常见于使用老旧Linux发行版的开发环境,…...
避开这3个坑!MATLAB匿名函数从入门到精通(2024新版)
避开这3个坑!MATLAB匿名函数从入门到精通(2024新版) 在工程计算和数据分析领域,MATLAB的匿名函数一直是提升代码灵活性的利器。然而,许多工程师在实际使用中常常陷入几个典型陷阱,导致代码效率低下甚至运行…...
Linux 0.11内核调试实战:手把手教你用Bochs+GDB定位第一次页故障(附完整答案)
Linux 0.11内核调试实战:从页故障到内存管理的深度探索 当你第一次在Linux 0.11内核实验中遇到页故障时,那种既兴奋又困惑的感觉可能还记忆犹新。作为操作系统学习者,理解页故障不仅是掌握内存管理的关键,更是通往内核深处的一扇门…...
Z-Image-Turbo LoRA Web服务GPU优化:显存碎片整理与长期运行稳定性保障
Z-Image-Turbo LoRA Web服务GPU优化:显存碎片整理与长期运行稳定性保障 1. 项目概述与核心价值 今天要跟大家分享的是一个基于Z-Image-Turbo模型的图片生成Web服务,重点解决了GPU显存管理和长期稳定运行的关键问题。这个服务不仅支持高质量的图片生成&…...
OpenClaw成本优化:Qwen3.5-9B自部署接口降低token消耗实践
OpenClaw成本优化:Qwen3.5-9B自部署接口降低token消耗实践 1. 为什么需要关注OpenClaw的token消耗? 去年夏天,当我第一次用OpenClaw自动化处理月度报表时,收到了令人咋舌的账单——短短一周的自动化操作消耗了价值近200美元的AP…...
三步搞定QQ空间历史说说备份:GetQzonehistory完整使用指南
三步搞定QQ空间历史说说备份:GetQzonehistory完整使用指南 【免费下载链接】GetQzonehistory 获取QQ空间发布的历史说说 项目地址: https://gitcode.com/GitHub_Trending/ge/GetQzonehistory 还在担心QQ空间的珍贵回忆会丢失吗?GetQzonehistory是…...
