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

3696. 构造有向无环图

Powered by:NEFU AB-IN

Link

文章目录

  • 3696. 构造有向无环图
    • 题意
    • 思路
    • 代码

3696. 构造有向无环图

  • 题意

    Codeforces Round 656 (Div. 3) E

    给定一个由 n个点和 m条边构成的图。
    不保证给定的图是连通的。
    图中的一部分边的方向已经确定,你不能改变它们的方向。
    剩下的边还未确定方向,你需要为每一条还未确定方向的边指定方向。
    你需要保证在确定所有边的方向后,生成的图是一个有向无环图(即所有边都是有向的且没有有向环的图)。

  • 思路

    自己想的思路,可能偏麻烦

    • 首先,将带方向的边连起来形成一个图g1,不带方向的边连起来,形成另一个图g
    • 其次,对g1进行拓扑排序 O(n+m)O(n+m)O(n+m)
      • 在拓扑排序途中,当遍历到一个节点u时
        • 首先判断,它是不是已经遍历过了,或者在g1图中,还有边指向它。如果存在其中一种情况,说明不能作为遍历的点,可以直接pop
      • 其次,可以得出结论,那么根据这个点u,在g图中遍历u的邻点v。首先,判断是否v已经在u前出队了,也就是拓扑序在前面,若没有的话,就在g图中连上 u到v的有向边,并且别忘了更新度
      • 后面就跟拓扑排序一样了
    • 最后,我们所有的边都在g1图中,那么dfs每个点,并标记,即可得出所有边
    • 另外,当g1图本身成环,或者,最后输出的拓扑序列不是n个,那么都是无解
  • 代码

    /*
    * @Author: NEFU AB-IN
    * @Date: 2023-03-01 23:23:00
    * @FilePath: \Acwing\3696\3696.cpp
    * @LastEditTime: 2023-03-01 23:58:06
    */
    #pragma GCC optimize(1)
    #pragma GCC optimize(2) // 先开优化
    #pragma GCC optimize(3, "Ofast", "inline")
    #include <bits/stdc++.h>
    using namespace std;
    #define int long long
    #undef int#define SZ(X) ((int)(X).size())
    #define ALL(X) (X).begin(), (X).end()
    #define IOS                                                                                                            \ios::sync_with_stdio(false);                                                                                       \cin.tie(nullptr);                                                                                                  \cout.tie(nullptr)
    #define DEBUG(X) cout << #X << ": " << X << '\n'
    typedef pair<int, int> PII;const int N = 3e5 + 10, INF = 0x3f3f3f3f;int deg[N];
    bool st[N], vis[N];
    void solve()
    {int n, m;cin >> n >> m;memset(st, 0, (n + 1));memset(deg, 0, (n + 1) * 4);memset(vis, 0, (n + 1));vector<int> g[n + 1], g1[n + 1];for (int i = 1; i <= m; ++i){int t, a, b;cin >> t >> a >> b;if (t){g1[a].push_back(b);deg[b]++;}else{g[a].push_back(b);g[b].push_back(a);}}queue<int> q;for (int i = 1; i <= n; ++i){if (!deg[i])q.push(i);}if (!SZ(q)){cout << "NO\n";return;}int cnt = 0;while (SZ(q)){auto u = q.front();q.pop();if (st[u] || deg[u])continue;for (auto &v : g[u]){if (!st[v]){g1[u].push_back(v);deg[v]++;}}st[u] = true; // 表示已经释放出去了cnt++;for (auto &v : g1[u]){if (!--deg[v]){q.push(v);}}}if (cnt != n){cout << "NO\n";return;}cout << "YES\n";function<void(int)> dfs = [&](int u) {vis[u] = 1;for (auto &v : g1[u]){cout << u << " " << v << '\n';if (!vis[v])dfs(v);}};for (int i = 1; i <= n; ++i){if (!vis[i])dfs(i);}return;
    }signed main()
    {IOS;int T;cin >> T;while (T--)solve();return 0;
    }
    

相关文章:

3696. 构造有向无环图

Powered by:NEFU AB-IN Link 文章目录3696. 构造有向无环图题意思路代码3696. 构造有向无环图 题意 Codeforces Round 656 (Div. 3) E 给定一个由 n个点和 m条边构成的图。 不保证给定的图是连通的。 图中的一部分边的方向已经确定&#xff0c;你不能改变它们的方向。 剩下的边…...

RuoYi-Flowable-Plus(代码生成)

RuoYi-Flowable-Plus搭建 若依所有扩展项目的代码生成功能都是一样的&#xff0c;RuoYi-Flowable-Plus为例来演示。 模块创建 1.创建新模块ruoyi-student2.编辑RuoYi-Flowable-Plus\pom.xml <dependency><groupId>com.ruoyi</groupId><artifactId>ruoy…...

训练CV模型常用的方法与技巧

最近参加一个CV比赛&#xff0c;看到有参赛者分享了自己训练图像识别模型时常用到的小技巧&#xff0c;故对其进行记录、整理&#xff0c;方便未来继续学习。整理了很多&#xff0c;它们不一定每次有用&#xff0c;但请记在心中&#xff0c;说不定未来某个任务它们就发挥了作用…...

[Java·算法·中等]LeetCode22. 括号生成

每天一题&#xff0c;防止痴呆题目示例分析思路1题解1分析思路2题解2分析思路3题解3&#x1f449;️ 力扣原文 题目 数字 n 代表生成括号的对数&#xff0c;请你设计一个函数&#xff0c;用于能够生成所有可能的并且 有效的 括号组合。 示例 输入&#xff1a;n 3 输出&…...

Git项目合并实践

Git项目合并实践 一、前言 环境 操作系统&#xff1a;Windows 10 专业版 代码托管平台&#xff1a;Gitee 场景 同一个项目&#xff0c;在某一个时间点&#xff0c;被另外一个团队拷贝和修改&#xff0c;并且代码不在同一个仓库&#xff0c;最后需要合并项目 不是同一个项…...

C++实战md5、base64算法实现(附源码)

C++常用功能源码系列 文章目录 C++常用功能源码系列前言一、常用加密算法1. md5是什么二、源码1. md52. base64、decode总结前言 本文是C/C++常用功能代码封装专栏的导航贴。部分来源于实战项目中的部分功能提炼,希望能够达到你在自己的项目中拿来就用的效果,这样更好的服务…...

P6专题:P6 EPPM和PPM基本概念

目录 引言 Oracles Primavera P6 Enterprise Project Portfolio Management&#xff08;P6 EPPM&#xff09; Oracles Primavera P6 Professional Project Management 引言 Oracle Primavera系列软件专注于项目密集型企业&#xff0c;其整个项目生命周期内所有项目的组合管…...

【为什么事务@Transactional会失效】

在Spring框架中&#xff0c;Transactional注解用于声明一个方法需要被包含在事务中&#xff0c;以确保数据库操作的一致性和完整性。Transactional注解通常用于Service层或DAO层的方法上。 Transactional注解失效可能是由以下原因引起的&#xff1a; 注解未被正确声明或配置&a…...

NLP中的对话机器人——模型的评估

引言 本文是七月在线《NLP中的对话机器人》的视频笔记&#xff0c;主要介绍FAQ问答型聊天机器人的实现。 模型的评估 我们如何评估模型的好坏&#xff1f;由于我们的数据集没有提供测试数据&#xff0c;所以我们很难评估模型的好 坏。如果我们要做非常严谨的评估&#xff0c…...

数据挖掘知识规整与心得体会

一.大数据的特点&#xff1a; 数据多&#xff0c;类型多&#xff0c;更新快&#xff0c;更新内容多。 二.分类&#xff08;classification&#xff09;与混淆矩阵&#xff08;confusion matrix&#xff09; 这里的分类说的是二分类问题&#xff0c;比如说把人分为好人和坏人&a…...

修正一些formdesigner的一些bug与操作

之前集成了formdesigner表单设计器&#xff0c;但还是有些问题&#xff0c;所以进行一些bug修复与功能修正 一、之前组件布局的图标不见了 在main.js里增加下面一行 import /components/formdesigner/assets/iconfont/iconfont.js 效果如下&#xff1a; 二、选择列表没有数…...

前端网络安全

什么是同源策略同源指的是&#xff1a;协议、端口号、域名必须一致。他是浏览器的一个用于隔离潜在恶意文件的重要安全机制。限制了从同一个源加载的文档或脚本&#xff0c;与另一个源的资源进行交互。同源策略主要限制了三个方面&#xff1a;当前域下的js脚本不能够访问其他域…...

docker内存统计

在docker里top和在docker外top看内存都是没有变化的&#xff0c;但是用docker stats看mem uasge就一直在涨top命令和docker stats命令采集内存使用的方式不同所致。top命令采集的是当前进程的内存使用情况&#xff0c;而docker stats命令采集的是整个Docker容器的内存使用情况。…...

【IDEA】IDEA使用有道翻译引擎—详细配置步骤

目录 前言 步骤一&#xff1a;下载翻译工具Translate 步骤二&#xff1a;注册登录有道云平台 步骤三&#xff1a;配置有道翻译 前言 2022年10月 谷歌翻译已经不在中国了&#xff0c;所以IDEA配置谷歌翻译会出错。 步骤一&#xff1a;下载翻译工具Translate 打开idea设置set…...

js求解《初级算法》56.最长公共前缀

一、题目描述 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀&#xff0c;返回空字符串 ""。 输入&#xff1a;strs ["flower","flow","flight"] 输出&#xff1a;"fl" 输入&#xff1a;strs ["…...

嵌入式Linux(二十四)系统烧写

将uboot&#xff0c;linux kernel&#xff0c;.dtb&#xff0c;rootfs烧写到板子上的EMMC上&#xff0c;避免断网导致不能运行。 1. MfgTool工具介绍 一路解压之后&#xff0c;得到以下两项&#xff1a; ①Profiles文件夹&#xff1a;后续烧写文件放到这个文件夹。  其中关注…...

【ECNU】3496. 贪吃的 xjj 和贪心的 oxx(C++)

目录 题目 输入格式 输出格式 样例 提示 思路 代码 题目 单点时限: 2.0 sec 内存限制: 256 MB oxx 与 xjj 终于到了 Xiamen&#xff0c;他们第一件事就是去吃当地著名的特产椰子饼。 他们共买了 n 盒礼盒&#xff0c;第 i 盒含 ai 块椰子饼。oxx 与 xjj 约定让 oxx …...

【iOS】设置背景渐变色

drawRect函数 主要负责iOS的绘图操作&#xff0c;程序会自动调用此方法进行绘图。我在这个函数中绘制渐变背景色。 方法定义&#xff1a; -(void)drawRect:(CGRect)rect; 重写此方法&#xff0c;执行重绘任务-(void)setNeedsDisplay; 标记为需要重绘&#xff0c;异步调用dra…...

Scrapy框架(高效爬虫)

文章目录一、环境配置二、创建项目三、scrapy数据解析四、基于终端指令的持久化存储1、基于终端指令2、基于管道3、数据同时保存至本地及数据库4、基于spider爬取某网站各页面数据5、爬取本页和详情页信息&#xff08;请求传参&#xff09;6、图片数据爬取ImagesPipeline五、中…...

程序设计语言-软件设计(二十一)

数据结构与算法&#xff08;二十&#xff09;快速排序、堆排序(四)https://blog.csdn.net/ke1ying/article/details/129269655 这篇主要讲的是 编译与解释、文法、正规式、有限自动机、表达式、传值与传址、多种程序语言特点。 编译的过程 解释型 和 编译型 编译型过程&#…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...