当前位置： 首页 > article >正文

P3916 图的遍历——反向建边dfs

article 来源：原创 2022/12/16 3:59:24

图的遍历

题目描述

给出 NNN 个点，MMM 条边的有向图，对于每个点 vvv，求 A(v)A(v)A(v) 表示从点 vvv 出发，能到达的编号最大的点。

输入格式

第 111 行 222 个整数 N,MN,MN,M，表示点数和边数。

接下来 MMM 行，每行 222 个整数 Ui,ViU_i,V_iUi​,Vi​，表示边 (Ui,Vi)(U_i,V_i)(Ui​,Vi​)。点用 1,2,…,N1,2,\dots,N1,2,…,N 编号。

输出格式

一行 NNN 个整数 A(1),A(2),…,A(N)A(1),A(2),\dots,A(N)A(1),A(2),…,A(N)。

样例 #1

样例输入 #1

4 3
1 2
2 4
4 3

样例输出 #1

4 4 3 4

提示

  • 对于 60%60\%60% 的数据，1≤N,M≤1031 \leq N,M \leq 10^31≤N,M≤103。
  • 对于 100%100\%100% 的数据，1≤N,M≤1051 \leq N,M \leq 10^51≤N,M≤105。

分析

  1. 此题的核心就是反向建边，因为如果直接从每个点开始爆搜的话，O(n^2)的复杂度怎么受得了 哈哈哈，所以要考虑新的做法；再看看这个题是干啥的，找每个点能到达的编号最大的点，那我们反过来，从最大的点开始出发，看看能到达谁，那所到达的点，它们的最大编号不就是出发那个点；
  2. 所以直接反向建边，然后从最大的编号n当做起点去找他能到达的点（那么 i 能到达的点，也就是那个点所能到达的最大编号），然后先从最大的编号n开始dfs，看看能到谁，把他们用数组A存起来，那么这些存起来的点，就是他们所能到达的最大编号的点；
#include <bits/stdc++.h>using namespace std;vector<int> g[100010];
int n, m;
int A[100010];void dfs(int u, int father) {//说明已找到能到达的最大编号了（因为是从编号最大的点开始反向找的）if (A[u])return;A[u] = father;for (int i = 0; i < g[u].size(); ++i) {dfs(g[u][i], father);}
}int main() {cin >> n >> m;int x, y;for (int i = 0; i < m; ++i) {cin >> x >> y;//反向建边g[y].push_back(x);}//反向建边的目的就是，从最大的编号当做起点去找他能到达的点（那么i到达的点，也就是那个点所能到达的最大编号）for (int i = n; i > 0; --i) {dfs(i, i);}for (int i = 1; i <= n; ++i) {cout << A[i] << " ";}return 0;
}

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章：

P3916 图的遍历——反向建边dfs

图的遍历 题目描述 给出 NNN 个点&#xff0c;MMM 条边的有向图&#xff0c;对于每个点 vvv&#xff0c;求 A(v)A(v)A(v) 表示从点 vvv 出发&#xff0c;能到达的编号最大的点。 输入格式 第 111 行 222 个整数 N,MN,MN,M&#xff0c;表示点数和边数。 接下来 MMM 行&…...

编程日记 2022/12/16 3:59:24

vpp hash源码分析

概述 vpp的hash结构分为hash头、桶&#xff08;_hash_create或hash_resize申请&#xff09;和桶下元素&#xff08;clib_mem_realloc申请&#xff09;&#xff0c;总共3个部分组成。 根据元素key的hash值不同&#xff0c;分配到不同的桶下&#xff0c;与其他hash表原理相同。 …...

编程日记 2022/12/16 3:58:49

Linux系统部署

Linux系统部署 下载vmware centos7 xshell6 xftp6新建虚拟机&#xff0c;注意设置网络连接&#xff0c;设置登录名&#xff1a;root,密码&#xff1a;root,等待登录&#xff0c;输入用户名和密码&#xff08;注意密码输入不显示&#xff09;登录成功&#xff0c;执行命令Ifc…...

编程日记 2022/12/16 3:58:13

单链表翻转-链表篇

leetcode206单链表的翻转 题目&#xff1a; 给你单链表的头节点 head &#xff0c;请你反转链表&#xff0c;并返回反转后的链表。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5] 输出&#xff1a;[5,4,3,2,1] 示例 2&#xff1a; 输入&#xff1a;head [1,2] 输出…...

编程日记 2022/12/16 3:57:35

Resnet18训练CIFAR10 准确率95%

准确率 95.31% 几个关键点&#xff1a; 1、改模型&#xff1a;原始的resnet18首层使用的7x7的卷积核&#xff0c;CIFAR10图片太小不适合&#xff0c;要改成3x3的&#xff0c;步长和padding都要一并改成1。因为图太小&#xff0c;最大池化层也同样没用&#xff0c;删掉。最后一…...

编程日记 2022/12/16 3:57:00

越来越多的纺织行业公司认证OEKO

【越来越多的纺织行业公司认证OEKO】 OEKO-TEX Standard 100是生态纺织品安全环保认证&#xff0c;即通过检测纺织品以及辅料是否含有OEKO-TEX限制的有害物质&#xff0c;人类穿着是否危害或者可能危害带人体的健康&#xff0c;它不是代表产品质量的质量标签&#xff0c;而是信…...

编程日记 2022/12/16 3:54:59

02.Ioc容器加载过程-Bean的生命周期源码深度剖析

Spring源码编译教程 Spring IoC容器的加载过程 process on脑图 1.实例化化容器&#xff1a;AnnotationConfigApplicationContext &#xff1a; // 加载spring上下文 AnnotationConfigApplicationContext context new AnnotationConfigApplicationContext(MainConfig.class);…...

编程日记 2022/12/16 3:54:20

物联网开发笔记（63）- 使用Micropython开发ESP32开发板之控制ILI9341 3.2寸TFT-LCD触摸屏进行LVGL图形化编程：显示中文

一、目的 这一节我们学习如何使用我们的ESP32开发板来控制ILI9341 3.2寸TFT-LCD触摸屏进行LVGL图形化编程的第一步&#xff1a;显示中文。 二、环境 ESP32 3.2寸 ILI9341触摸屏 Thonny IDE 几根杜邦线 Win10 接线方法&#xff1a;请看上一篇文章。 三、流程介绍 …...

编程日记 2022/12/16 3:53:43

jsp+ssm计算机毕业设计毕业论文管理系统【附源码】

项目运行 环境配置&#xff1a; Jdk1.8 Tomcat7.0 Mysql HBuilderX&#xff08;Webstorm也行&#xff09; Eclispe&#xff08;IntelliJ IDEA,Eclispe,MyEclispe,Sts都支持&#xff09;。 项目技术&#xff1a; JSPSSM mybatis Maven等等组成&#xff0c;B/S模式 Mave…...

编程日记 2022/12/16 3:53:08

net基于asp.net的社区团购网站-计算机毕业设计

项目介绍 社区团购系统依托社区团购系统和社区门店,是现在的一个重大市场和发展方向,通过研究企业在社区团购系统环境下的营销模式创新,对于普通的零售业和传统社区团购系统的转型发展具有重要的理论意义。随着互联网行业的发展,人们的生活方式发生着重大变化,人们越来越倾向于…...

编程日记 2022/12/16 3:51:03

Capstone芯片方案设计介绍|CS拓展坞功能说明|CS原厂推荐功能型号

Capstone科技于2018年8月在台湾成立。团队成员的多样性将硅谷和台湾的才华横溢的人联系在一起&#xff0c;以进行协作和取得卓越成就。 Capstone科技是由一个经验丰富的研发团队建立的&#xff0c;该团队专注于研发交付高速接口连接和多媒体应用的竞争解决方案&#xff0c;广泛…...

编程日记 2023/3/29 1:20:57

1 gazebo打不开一直卡在Preparing your world

1 gazebo打不开一直卡在"Preparing your world"1 gazebo打不开一直卡在"Preparing your world"主要问题解决方法1 gazebo打不开一直卡在"Preparing your world" 主要问题 在运行某些程序的功能包的时候&#xff0c;gazebo启动的时候会一直卡在…...

编程日记 2023/3/29 1:17:53

调试错误：Invalid arg tag: environment variable 'TURTLEBOT_GAZEBO_WORLD_FILE' is not set.

调试错误&#xff1a;Invalid tag: environment variable ‘TURTLEBOT_GAZEBO_WORLD_FILE’ is not set. 1.问题描述 在终端输入roslaunch turtlebot_gazebo turtlebot_world.launch时&#xff0c;出现以下错误&#xff1a; ~$ roslaunch turtlebot_gazebo turtlebot_world.…...

编程日记 2023/3/29 1:17:53

Ubuntu 16.04下gazebo7的安装方法

Ubuntu 16.04下gazebo的安装方法 1.卸载当前已安装的不能运行的gazebo相关包 (1)查找当前安装的gazebo包 dpkg -l | grep gazebo(2)卸载 sudo apt-get remove gazebo7 gazebo7-common gazebo7-plugin-base libgazebo7:amd64 libgazebo7-dev:amd642.安装能运行版本gazebo软件…...

编程日记 2023/3/29 1:17:52

让turtlebot动起来并且显示相机拍到的画面

让turtlebot动起来并且显示相机拍到的画面 1.启动仿真环境&#xff0c;在gazebo中显示机器人 打开新的终端输入&#xff1a; roscore打开新的终端输入&#xff1a; roslaunch turtlebot_gazebo turtlebot_world.launch显示如下: 2.用键盘进行控制机器人 2.1 打开新的终端…...

编程日记 2023/3/29 1:17:52

在gazebo中运行turtlebot模拟gmapping过程

在gazebo中运行turtlebot模拟gmapping过程 1.启动Gazebo并加载机器人、环境模型 roslaunch turtlebot_gazebo turtlebot_world.launch2.启动键盘遥控节点 roslaunch turtlebot_teleop keyboard_teleop.launch --screen3.运行gmapping roslaunch turtlebot_gazebo gmapping_…...

编程日记 2023/3/29 1:17:51

gazebo 编辑模拟世界

roslaunch turtlebot_gazebo turtlebot_world.launch world_file:/opt/ros/kinetic/share/turtlebot_gazebo/worlds/corridor.worldecho $TURTLEBOT_GAZEBO_WORLD_FILE 输出&#xff1a; /opt/ros/kinetic/share/turtlebot_gazebo/worlds/playground.world您可以更新它&#xf…...

编程日记 2023/3/29 1:17:50

gazebo+turtlebot教程

gazeboturtlebot教程 编辑模拟世界&#xff1a; http://learn.turtlebot.com/2015/02/03/6/ 编写第一个脚本&#xff1a; http://learn.turtlebot.com/2015/02/03/7/...

编程日记 2023/3/29 1:17:50

gazebo——在gazebo中运行turtlebot机器人模拟gmapping的slam过程

在gazebo中运行turtlebot机器人模拟gmapping的slam过程 https://blog.csdn.net/lingchen2348/article/details/79503970...

编程日记 2023/3/29 1:17:49

gazebo——解决第一次打开gazebo卡的时间特别久问题

解决第一次打开gazebo卡的时间特别久问题 $ cd ~/.gazebo/ $ mkdir -p models $ cd ~/.gazebo/models/ $ wget http://file.ncnynl.com/ros/gazebo_models.txt $ wget -i gazebo_models.txt $ ls model.tar.g* | xargs -n1 tar xzvf...

编程日记 2023/3/29 1:17:49