当前位置: 首页 > 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 这篇主要讲的是 编译与解释、文法、正规式、有限自动机、表达式、传值与传址、多种程序语言特点。 编译的过程 解释型 和 编译型 编译型过程&#…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...