【图论】基环树

基环树其实并不是树,是指有n个点n条边的图,我们知道n个点n-1条边的连通图是树,再加一条边就会形成一个环,所以基环树中一定有一个环,长下面这样:
在这里插入图片描述
由基环树可以引申出基环内向树基环外向树

基环内向树如下,特点是每个点的出度为1
在这里插入图片描述
基环外向树如下,特点是每个点的入度为1
在这里插入图片描述
下面放点题,做到相关题目随时更新

基环树+组合数学

CF 1454E Number of Simple Paths

先记录环上的点,每个环上的点引出去的子树中,两点之间都只有一条路径,然后子树和其他点之间都有两条路径(因为有个环),可以循环计算每个子树,答案累加即可

#include <bits/stdc++.h>using namespace std;typedef pair<int, int> PII;#define int long longvoid solve()
{int n;cin >> n;vector<vector<int>> g(n + 1);vector<int> in(n + 1);for (int i = 0 ;i < n; i ++ ){int a, b;cin >> a >> b;g[a].push_back(b);g[b].push_back(a);in[a] ++ , in[b] ++ ;}queue<int> q;for (int i = 1; i <= n; i ++ ) {if (in[i] == 1) q.push(i);}while (q.size()){auto t = q.front();q.pop();for (int i = 0; i < g[t].size(); i ++ ){int j = g[t][i];in[j] -- ;if (in[j] == 1) q.push(j);}}vector<int> huan;vector<int> st(n + 1);for (int i = 1; i <= n; i ++ ){if (in[i] > 1){huan.push_back(i);st[i] = true;}}int ans = 0, sumtmp, sum = 0;vector<bool> visited(n + 1);function<void(int, int)> dfs = [&](int u, int fa){sumtmp ++ ;if (visited[u]) return;visited[u] = true;for (int i = 0; i < g[u].size(); i ++ ){int j = g[u][i];if (j == fa || visited[j] || st[j]) continue;dfs(j, u);}return;};for (auto i : huan){sumtmp = 0;dfs(i, -1);ans += sumtmp * (sumtmp - 1) / 2;ans += (sumtmp - 1) * (n - sumtmp - sum) * 2;sum += sumtmp - 1;}ans += huan.size() * (huan.size() - 1);cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t -- ){solve();}
}

基环内向树+dfs

牛客 寒假集训1K 牛镇公务员考试

基环内向树(准确的说应该是森林)

编号 i 向 a[i] 连边,表示对其限制,我们可以发现环之外的链对答案没什么影响,因为确定了环上一点,可以倒推出链上的所有答案(原因就是约束关系),所以我们在环上任取一点,枚举这个点的五种答案,然后遍历一下环看这个答案是否合法

因为不保证联通,所以需要遍历每一个点

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;const int N = 1000010;
const int maxn = 1e6 + 1;
const int mod = 998244353;void solve()
{int n;cin >> n;vector<int> a(n + 1);vector<string> s(n + 1);for (int i = 1; i <= n; i ++ ) cin >> a[i] >> s[i];vector<bool> st(n + 1);int ans = 1;for (int i = 1; i <= n; i ++ ){if (st[i]) continue;int j = i;vector<int> huan;for (; !st[j]; j = a[j]){huan.push_back(j);st[j] = true;}auto iter = find(huan.begin(), huan.end(), j);if (iter == huan.end()) continue;huan = {iter, huan.end()};int tmp = 0;for (int k = 0; k < 5; k ++ ){int h = k;for (auto t : huan) h = (int)(s[t][h] - 'A');tmp += h == k;}ans = ans * tmp % mod;}cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t -- ){solve();}
}

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

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

相关文章

学习VR全景拍摄,如何选择适合的VR全景设备?

随着VR全景技术的不断成熟和发展&#xff0c;VR全景已经成为摄影爱好者、地产行业、中介经纪人、广告、企业宣传等行业从业者们乐于尝试的新领域、新手段。 如何选择合适的VR全景设备成为了一个重要的问题。今天&#xff0c;和大家聊一聊&#xff0c;不同行业、人群和用途更适合…

【Qt】Android上运行keeps stopping, Desktop上正常

文章目录 问题 & 背景背景问题 解决方案One More ThingTake Away 问题 & 背景 背景 在文章【Qt】最详细教程&#xff0c;如何从零配置Qt Android安卓环境中&#xff0c;我们在Qt中配置了安卓开发环境&#xff0c;并且能够正常运行。 但笔者在成功配置并完成上述文章…

【蓝桥杯冲冲冲】[NOIP2017 提高组] 宝藏

蓝桥杯备赛 | 洛谷做题打卡day29 文章目录 蓝桥杯备赛 | 洛谷做题打卡day29[NOIP2017 提高组] 宝藏题目背景题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1样例 #2样例输入 #2样例输出 #2提示题解代码我的一些话[NOIP2017 提高组] 宝藏 题目背景 NOIP2017 D2T2 题目描…

ChatGPT辅助编程,一次有益的尝试

如果大家想学习PCIe&#xff0c;搜索网上的信息&#xff0c;大概率会看到chinaaet上Felix的PCIe扫盲系列的博文 Felix-PCIe扫盲 每次看这个系列博文的时候&#xff0c;我都在想有没有什么方法可以把这个系列的博文都保存到一个pdf文件中&#xff0c;这样方便阅读。于是有了下…

tkinter绘制组件(41)——菜单按钮

tkinter绘制组件&#xff08;41&#xff09;——菜单按钮 引言布局函数结构按钮部分菜单显示完整代码函数 效果测试代码最终效果 github项目pip下载结语 引言 TinUI5的新控件&#xff0c;菜单按钮&#xff0c;menubutton。 这是一个与TinUI菜单&#xff08;menubar&#xff0…

算法之双指针系列1

目录 一&#xff1a;双指针的介绍 1&#xff1a;快慢指针 2&#xff1a;对撞指针 二&#xff1a;对撞指针例题讲述 一&#xff1a;双指针的介绍 在做题中常用两种指针&#xff0c;分别为对撞指针与快慢指针。 1&#xff1a;快慢指针 简称为龟兔赛跑算法&#xff0c;它的基…

上海泗博HART转ModbusTCP网关HME-635应用案例之组态王和超声波液位计通信

如今工业现场的应用也逐渐把现场的不同应用协议转换成以太网&#xff0c;以此来提升现场的通信速度和质量。Modbus TCP是工业以太网协议的一种&#xff0c;也是现场应用中最常使用的。本应用案例是基于Modbus TCP的组态王和基于HART的超声波液位计之间数据通讯的具体应用。 应用…

STM32F407 CAN参数配置 500Kbps

本篇CAN参数适用 芯片型号&#xff1a;STM32F407xx系统时钟&#xff1a;168MHz&#xff0c;CAN挂载总线APB1为42M波 特 率 &#xff1a;500Kpbs引脚使用&#xff1a;TX_PB9&#xff0c;RX_PB8&#xff1b;修改为PA11PA12后&#xff0c;参数不变。 步骤一、打勾开启CAN&#xf…

vector类的模拟实现

实现基本的vector框架 参考的是STL的一些源码&#xff0c;实现的vector也是看起来像是一个简略版的&#xff0c;但是看完能对vector这个类一些接口函数更好的认识。 我们写写成员变量&#xff0c;先来看看STL的成元变量是那些 namespace tjl {template<class T>class …

无损音乐下载,最新音乐下载,mp3格式音乐下载,一键下载mp3格式音乐,我只用这个软件,歌曲资源丰富,全网音乐免费下载,稳定运行,告别收费

一、软件简介 现在很多支持一键下载mp3音乐/无损音质音乐的音乐播放器通常都是解析接口套了一个壳&#xff0c;一旦解析接口失效&#xff0c;软件就不能下载音乐了&#xff0c;因此一个稳定的解析接口是这类软件最大的保障。本次小编推荐的音乐下载软件接口非常稳定&#xff0…

C语言:函数

创作不易&#xff0c;友友们给个三连吧&#xff01;&#xff01; 一、函数的概念 数学中我们见过函数的概念&#xff0c;例如ykxb&#xff0c;k和b都是常数&#xff0c;给任意一个x就可以得到y 而C语言也引入了函数&#xff08;function&#xff09;这个概念&#xff0c;C语…

利用LLM大模型生成sql的深入应用探究

Chat2DB 是一款有开源免费的多数据库客户端工具,和传统的数据库客户端软件Navicat、DBeaver 相比 Chat2DB 集成了 AIGC 的能力&#xff0c;能够将自然语言转换为 SQL&#xff0c;也可以将 SQL 转换为自然语言&#xff0c;可以给出研发人员 SQL 的优化建议&#xff0c;极大地提升…

初识C语言·预处理详解

目录 1 预定义符号 2 define定义常量 3 #define定义宏 4 带有副作用的宏 5 宏替换的规则 6 宏和函数的对比 7 # 和 ## i) #运算符 ii) ##运算符 8 命名约定 9 命令行定义 10 条件编译 条件编译1&#xff1a; 条件编译2&#xff1a; 条件编译3&#xff1a; 条件…

单片机学习笔记---LED点阵屏的工作原理

目录 LED点阵屏分类 LED点阵屏显示原理 74HC595的介绍 一片74HC595的工作原理 多片级联工作原理 总结 LED点阵屏由若干个独立的LED组成&#xff0c;LED以矩阵的形式排列&#xff0c;以灯珠亮灭来显示文字、图片、视频等。LED点阵屏广泛应用于各种公共场合&#xff0c;如汽…

鸿蒙(HarmonyOS)项目方舟框架(ArkUI)之ScrollBar组件

鸿蒙&#xff08;HarmonyOS&#xff09;项目方舟框架&#xff08;ArkUI&#xff09;之ScrollBar组件 一、操作环境 操作系统: Windows 10 专业版、IDE:DevEco Studio 3.1、SDK:HarmonyOS 3.1 二、ScrollBar组件 鸿蒙&#xff08;HarmonyOS&#xff09;滚动条组件ScrollBar&…

Logback - 日志框架

引言 在当今的企业级应用开发中&#xff0c;日志管理是一个不可或缺的部分。它不仅帮助我们进行错误跟踪&#xff0c;还能有效监控应用程序的运行状态&#xff0c;为性能优化提供数据支撑。Spring Boot作为一个简化Spring应用开发的框架&#xff0c;自带了强大的日志管理功能。…

如何用python进行数据分析?

前言 很多人可能会有这样的疑问&#xff0c;数据分析Excel挺强大的&#xff0c;会Excel就行&#xff0c;为什么还要去学python&#xff1f; 是的&#xff0c;Excel和python对于数据分析而言&#xff0c;这两者都只是不同的工具而已。 但&#xff0c;有一点我们要考虑&#x…

iOS 需求 多语言(国际化)App开发 源码

一直觉得自己写的不是技术&#xff0c;而是情怀&#xff0c;一个个的教程是自己这一路走来的痕迹。靠专业技能的成功是最具可复制性的&#xff0c;希望我的这条路能让你们少走弯路&#xff0c;希望我能帮你们抹去知识的蒙尘&#xff0c;希望我能帮你们理清知识的脉络&#xff0…

路由器、路由器的构成、交换结构

目录 1 路由器 1.1 路由器的结构 “转发”和“路由选择”的区别 1.1.1 输入端口对线路上收到的分组的处理 1.1.2 输出端口将交换结构传送来的分组发送到线路 2.2 交换结构 2.2.1 通过存储器 2.2.2 通过总线 2.2.3 通过纵横交换结构 (crossbar switch fabric) 1 路由器…

BUGKU-WEB 留言板

题目描述 题目无需登录后台&#xff01;需要xss平台接收flag&#xff0c; http协议需要http协议的xss平台打开场景后界面如下&#xff1a; 解题思路 看到此类的题目&#xff0c;应该和存储型xss有关&#xff0c;也就是将恶意代码保存到服务器端即然在服务器端&#xff0c;那就…