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

【PTA Advanced】1146 Topological Order(C++)

目录

题目

Input Specification:

Output Specification:

Sample Input:

Sample Output:

思路

C++ 知识UP

代码


题目

This is a problem given in the Graduate Entrance Exam in 2018: Which of the following is NOT a topological order obtained from the given directed graph? Now you are supposed to write a program to test each of the options.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N (≤ 1,000), the number of vertices in the graph, and M (≤ 10,000), the number of directed edges. Then M lines follow, each gives the start and the end vertices of an edge. The vertices are numbered from 1 to N. After the graph, there is another positive integer K (≤ 100). Then K lines of query follow, each gives a permutation of all the vertices. All the numbers in a line are separated by a space.

Output Specification:

Print in a line all the indices of queries which correspond to "NOT a topological order". The indices start from zero. All the numbers are separated by a space, and there must no extra space at the beginning or the end of the line. It is graranteed that there is at least one answer.

Sample Input:

6 8
1 2
1 3
5 2
5 4
2 3
2 6
3 4
6 4
6
5 2 3 6 4 1
1 5 2 3 6 4
5 1 2 6 3 4
5 1 2 3 6 4
5 2 1 6 3 4
1 2 3 4 5 6

Sample Output:

0 4 5

思路

难度评级:⭐️

1. 用邻接表存储图时,所用的空间和时间都会比较少;

        邻接表可以用vector<int> list[n]的形式;

2. 判断一个序列是否是拓扑序列时,只需要判断序列中每一个顶点在当时情况下的入度是否为0,为0后,则需要将其所指向的结点的入度都-1,重复该步骤;

3. 所以顶点的入度是比较常用的性质,应该用数组去存储,这样就可以避免每次都去遍历邻接表了,节省了时间

4. "a topological order"是拓扑序列的意思

C++ 知识UP

1. 一维数组的拷贝

一维数组可以直接拷贝到一个vector类型的容器中,方法如下:

vector<int> vec(arr, arr+n);// arr是一维数组,n是arr元素个数

也可以拷贝进另一个一维数组,方法如下:

copy(begin(arr), end(arr), begin(arrCopy)); 

2. 二维数组的拷贝

copy(&arr[0][0], &arr[0][0] + m * n, &arrCopy[0][0]); 

代码

#include <iostream>
#include <vector>using namespace std;int main(int argc, char** argv) {int n,m;cin>>n>>m;int in[1001]={0};// 统计各个顶点的入度 vector<int> list[1001];// 邻接表记录图结构 for(int i=0;i<m;i++) {int a,b;cin>>a>>b;list[a].push_back(b);in[b]++;}int K;cin>>K;bool flagOfSpace=false;for(int i=0;i<K;i++) {vector<int> order(n);for(int j=0;j<n;j++) cin>>order[j];vector<int> tin(in,in+n+1);// 检查每个顶点bool flagOfOrder=true;for(int j=0;j<n;j++) {int v=order[j]; // 检查顶点v的入度是否为0if(tin[v]!=0) {flagOfOrder=false;break; } // 从v出发指向的顶点的入度统统-1for(int x:list[v]) {tin[x]--;} }if(!flagOfOrder) {if(flagOfSpace) cout<<" ";flagOfSpace=true;cout<<i;}}return 0;
}

相关文章:

【PTA Advanced】1146 Topological Order(C++)

目录 题目 Input Specification: Output Specification: Sample Input: Sample Output: 思路 C 知识UP 代码 题目 This is a problem given in the Graduate Entrance Exam in 2018: Which of the following is NOT a topological order obtained from the given dire…...

基于stm32mp157的嵌入式linux+qt项目实战物联网毕业设计选题之智慧医疗项目

stm32mp157开发板FS-MP1A是华清远见自主研发的一款高品质、高性价比的Linux单片机二合一的嵌入式教学级开发板。开发板搭载ST的STM32MP157高性能微处理器&#xff0c;集成2个Cortex-A7核和1个Cortex-M4 核&#xff0c;A7核上可以跑Linux操作系统&#xff0c;M4核上可以跑FreeRT…...

Java实现邮件发送功能

确定发件人邮箱和密码某些邮箱服务器为了增加邮箱本身密码的安全性,给 SMTP 客户端设置了独立密码(有的邮箱称为“授权码”) 对于开启了独立密码的邮箱, 这里的邮箱密码必需使用这个独立密码(授权码) 确认发件人邮箱的 SMTP 服务器地址发件人邮箱的 SMTP 服务器地址, 必须…...

springboot+vue简单对接支付宝完整流程

源码 前端 vue-demo https://www.aliyundrive.com/s/dmnY8G6N6RM 点击链接保存&#xff0c;或者复制本段内容&#xff0c;打开「阿里云盘」APP &#xff0c;无需下载极速在线查看&#xff0c;视频原画倍速播放。 后端 aliPay https://www.aliyundrive.com/s/H2JFBjGWuf2 …...

Map 查找表

Map体现的结构是一个多行两列的表格,其中左列称为key,右列称为value.Map总是成对保存数据,并且总是根据key获取对应的value.因此我们可以将查询的条件作为key查询对应的结果作为value保存到Map中.Map有一个要求:key不允许重复(equals比较的结果)java.util.Map接口,是所有Map的顶…...

python--石头剪刀布游戏(列表)

本使用了下面几篇文章的知识&#xff1a; python(8)--列表初阶使用_码银的博客-CSDN博客 python(7)--if语句_码银的博客-CSDN博客 一、学习目标 利用列表实现石头剪刀布游戏 二、实验环境 Pycharm社区版、win11 三、代码 先贴代码&#xff0c;有需要的直接拿&#xff0c;想要进…...

Project Caliper:目标是打造最佳VR手柄

一提到Valve Index&#xff0c;人们很快联想到它的五指追踪VR手柄&#xff0c;这款支持手势追踪和体感反馈的高端VR手柄&#xff0c;是市面上最强大的C端VR手柄之一。尽管如此&#xff0c;它依然存在许多缺陷&#xff0c;比如配备的小型摇杆质量不佳、集成式设计不利于维修、人…...

自动驾驶:BEV开山之作LSS(lift,splat,shoot)原理代码串讲

自动驾驶&#xff1a;BEV开山之作LSS&#xff08;lift,splat,shoot&#xff09;原理代码串讲前言Lift参数创建视锥CamEncodeSplat转换视锥坐标系Voxel Pooling总结前言 目前在自动驾驶领域&#xff0c;比较火的一类研究方向是基于采集到的环视图像信息&#xff0c;去构建BEV视角…...

C# 如何实现对“属性”的扩展

目录一、为什么要扩展属性二、如何做&#xff1f;一、为什么要扩展属性 属性是一个类的特征&#xff0c;随着开发的不断升级&#xff0c;这种特征可能在一直变化&#xff0c;有时候为了向下兼容&#xff0c;一般属性的数量都是直接递增的。 例如&#xff1a;一个Person类&…...

EBS 物料属性 先后台对应关系 MTL_SYSTEM_ITEMS_B

Introductionweb The basic table mtl_system_items_b is the basic table of item in ERP system and there are a lot of columns,but I don’t know used of each column,particularly the column like %_flag. The reason of general exception may be because the ‘%_fl…...

MYSQL数据库-主从复制(原理及搭建)

文章目录1 概述2 原理3 搭建3.1 主库配置3.2 从库配置1 概述 主从复制是指将主数据库的DDL和 DML操作通过二进制日志传到从库服务器中&#xff0c;然后在从库上对这些日志重新执行(也叫重做)&#xff0c;从而使得从库和主库的数据保持同步。 MySQL支持一台主库同时向多台从库进…...

3GPP-NR Band25标准定义频点和信道(3GPP V17.7.0 (2022-12))

Reference test frequencies for NR operating band n25 Table 4.3.1.1.1.25-1: Test frequencies for NRoperating band n25 and SCS 15 kHz CBW [MHz]carrierBandwidth...

微信小程序 之 原生开发

目录 一、前期预备 1. 预备知识 ​2. 注册账号 - 申请AppID 3. 下载小程序开发工具 4. 小程序项目结构 ​5. 小程序的MVVM架构 二、创建小程序项目 1. 查看注册的appId ​2. 创建项目 ​3. 新建页面 01 - 创建text页面文件夹 ​02 - 新建text的page ​03 - 在app.json中配置 ​…...

常用vim命令和vim基本使用及Linux用户的管理,用户和组相关文件

常用vim命令和vim基本使用及Linux用户的管理&#xff0c;用户和组相关文件1. vim 的基本介绍和使用1.1 vim的三种模式1.2 常用vim命令【小白】1.3 Vim键盘图&#xff1a;2. Linux用户管理2.1 添加用户2.2 删除用户2.3 修改账号3. Linux系统用户组的管理4. 用户和组相关文件4.1 …...

阿里云服务器部署前后端分离项目

阿里云服务器部署 【若依】 前后端分离项目 文章目录一、域名解析二、服务器操作系统置空三、部署方式四、需安装环境配置五、Linux服务器安装相应内容&#xff08;具体安装步骤&#xff09;&#xff08;一&#xff09;安装JDK&#xff08;3种方式&#xff09;使用Yum安装&…...

内核经典数据结构list 剖析

前言&#xff1a;linux内核中有很多经典的数据结构&#xff0c;list(也称list_head)为其中之一&#xff0c;这些数据结构都是使用C语言实&#xff0c;并且定义和实现都在单独的头文件list.h中。可以随时拿出来使用。list.h的定义不同linux发行版本路径不同,我们可以在/usr/incl…...

华为OD机试 - 考优选核酸检测点(Python)| 真题+思路+考点+代码+岗位

优选核酸检测点 题目 张三要去外地出差,需要做核酸,需要在指定时间点前做完核酸, 请帮他找到满足条件的核酸检测点。 给出一组核酸检测点的距离和每个核酸检测点当前的人数给出张三要去做核酸的出发时间 出发时间是 10 分钟的倍数 同时给出张三做核酸的最晚结束时间题目中…...

在魔改PLUS-F5280开发板上使用合封qsp iflash

文章目录引言硬件调整软件调整总结引言 由于目前灵动官网暂未发布正式版的PLUS-F5280开发板&#xff0c;可以使用现有的PLUS-F5270 v1.2开发板&#xff08;下文简称PLUS-F5270开发版&#xff09;替换为MM32F5280微控制器芯片&#xff0c;改装为PLUS-F5280开发板。本文记录了使…...

uni-app 瀑布流

效果图 一、组件 components/u-myWaterfall.vue <template><view class"u-waterfall"><view id"u-left-column" class"u-column"><slot name"left" :leftList"leftList"></slot></view&…...

华为OD机试 - 去除多余空格(Python)| 真题+思路+考点+代码+岗位

去除多余空格 题目 去除文本多余空格,但不去除配对单引号之间的多余空格。给出关键词的起始和结束下标,去除多余空格后刷新关键词的起始和结束下标。 条件约束: [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-oQABYuJD-1676475739950)(https://…...

毕设代码二手房数据实战:从爬取到可视化的一站式工程实现

最近在帮学弟学妹看计算机专业的毕业设计&#xff0c;发现“二手房数据分析”真是个热门选题。想法都挺好&#xff0c;但一到动手实现&#xff0c;很多人就卡在了数据上&#xff1a;要么网站反爬太严数据抓不下来&#xff0c;要么抓下来的数据乱七八糟没法用&#xff0c;好不容…...

OpenClaw技能市场巡礼:GLM-4.7-Flash支持的10个实用自动化模块

OpenClaw技能市场巡礼&#xff1a;GLM-4.7-Flash支持的10个实用自动化模块 1. 为什么需要关注OpenClaw技能市场&#xff1f; 去年冬天&#xff0c;我花了整整两周时间手动整理公司邮箱里堆积如山的会议记录和客户邮件。每天重复着"下载附件-重命名-分类存储"的机械…...

嵌入式软件分层架构设计与RTOS抽象实践

通用嵌入式软件架构分层设计实践指南1. 项目概述1.1 系统架构设计背景在嵌入式系统开发中&#xff0c;随着项目复杂度提升&#xff0c;代码组织混乱、可维护性差成为常见问题。特别是在使用STM32、GD32等主流单片机时&#xff0c;缺乏合理的软件分层设计会导致以下问题&#xf…...

VBA Collection对象实战:从Excel数据处理到自动化报表的5个高效技巧

VBA Collection对象实战&#xff1a;从Excel数据处理到自动化报表的5个高效技巧 在Excel自动化领域&#xff0c;VBA的Collection对象就像瑞士军刀中的主刀——看似简单却功能强大。不同于数组的刻板和字典的复杂&#xff0c;Collection以轻量级特性成为处理动态数据的理想选择。…...

【2026年小红书春招- 3月25日 -第一题- 数据库】(题目+思路+JavaC++Python解析+在线测试)

题目内容 小红书数据库中有用户编号、用户名称和用户经验三个字段,其中: 用户编号为 111 到 10910^910...

【日记】本周末只休息一下午(999 字)

正文 周五下班&#xff0c;非常疲倦。点了个外卖&#xff0c;倒在床上睡了。等外卖小哥打电话叫我。睡了大概有半个小时吧。 睡觉确实是回血速度最快的方式了。 今天和明天都要加班&#xff0c;守着工人干活儿。 昨天基本全天都守着&#xff0c;因为要沿着 11 楼楼顶把管道铺到…...

阿里悟空 vs 腾讯龙虾:大厂 AI 自动化对决,普通人该怎么选?

最近 AI 自动化圈彻底炸了,一边是钉钉推出的阿里悟空,主打企业级合规与深度协同;另一边是腾讯全系铺开的龙虾(QClaw/WorkBuddy),靠着微信遥控、零门槛上手刷屏全网。 很多技术小白、职场人都在跟风 “养龙虾”,但这两个产品到底差在哪?腾讯龙虾真的适合所有人吗?今天…...

从SEO到GEO:网络设备厂商必学的AI时代内容优化新技能

从SEO到GEO&#xff1a;网络设备厂商必学的AI时代内容优化新技能 当ChatGPT在2022年底横空出世时&#xff0c;很少有人能预料到生成式AI会如此迅速地重塑整个技术信息的传播格局。对于网络设备厂商而言&#xff0c;这场变革来得尤为猛烈——传统的关键词堆砌、外链建设等SEO手段…...

foobox-cn终极美化方案:为foobar2000打造专业级音乐播放体验

foobox-cn终极美化方案&#xff1a;为foobar2000打造专业级音乐播放体验 【免费下载链接】foobox-cn DUI 配置 for foobar2000 项目地址: https://gitcode.com/GitHub_Trending/fo/foobox-cn foobox-cn是一款基于DUI&#xff08;DirectUI&#xff09;架构的foobar2000皮…...

专精特新企业品牌升级实操:把技术专长转换成客户敢选的购买理由

最容易做错的一步&#xff0c;不是没做&#xff0c;而是把“专精特新企业品牌升级”做成了换壳&#xff1a;标题换了&#xff0c;结构没换&#xff1b;字数变了&#xff0c;判断逻辑没变。一、问题定义很多专精特新企业都会遇到一种很委屈的状态&#xff1a;客户见完之后说“你…...