卡码网KamaCoder 117. 软件构建
题目来源:117. 软件构建


C++题解(来源代码随想录):拓扑排序:给出一个 有向图,把这个有向图转成线性的排序。拓扑排序也是图论中判断有向无环图的常用方法。
拓扑排序的过程,其实就两步:
- 找到入度为0 的节点,加入结果集
- 将该节点从图中移除
循环以上两步,直到 所有节点都在图中被移除了。
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
int main() {int m, n, s, t;cin >> n >> m;vector<int> inDegree(n, 0); // 记录每个文件的入度unordered_map<int, vector<int>> umap;// 记录文件依赖关系vector<int> result; // 记录结果while (m--) {// s->t,先有s才能有tcin >> s >> t;inDegree[t]++; // t的入度加一umap[s].push_back(t); // 记录s指向哪些文件}queue<int> que;for (int i = 0; i < n; i++) {// 入度为0的文件,可以作为开头,先加入队列if (inDegree[i] == 0) que.push(i);//cout << inDegree[i] << endl;}// int count = 0;while (que.size()) {int cur = que.front(); // 当前选中的文件que.pop();//count++;result.push_back(cur);vector<int> files = umap[cur]; //获取该文件指向的文件if (files.size()) { // cur有后续文件for (int i = 0; i < files.size(); i++) {inDegree[files[i]] --; // cur的指向的文件入度-1if(inDegree[files[i]] == 0) que.push(files[i]);}}}if (result.size() == n) {for (int i = 0; i < n - 1; i++) cout << result[i] << " ";cout << result[n - 1];} else cout << -1 << endl;}
相关文章:
卡码网KamaCoder 117. 软件构建
题目来源:117. 软件构建 C题解(来源代码随想录):拓扑排序:给出一个 有向图,把这个有向图转成线性的排序。拓扑排序也是图论中判断有向无环图的常用方法。 拓扑排序的过程,其实就两步࿱…...
Acwing 线性DP
状态转移方程呈现出一种线性的递推形式的DP,我们将其称为线性DP。 Acwing 898.数字三角形 实现思路: 对这个三角形的数字进行编号,状态表示依然可以用二维表示,即f(i,j),i表示横坐标(横线),j表…...
Docker面试-24年
1、Docker 是什么? Docker一个开源的应用容器引擎,是实现容器技术的一种工具,让开发者可以打包他们的应用以及环境到一个镜像中,可以快速的发布到任何流行的操作系统上。 2、Docker的三大核心是什么? 镜像:Docker的…...
ubuntu 安装k8s
#关闭 Swap 内存,配置完成建议重启一下 nano /etc/fstab #注释下面相似的一行 #/swapfile none swap sw 0 0 #重启 reboot#部属k8s apt update && apt install -y apt-transport-https 下载 gpg 密钥 curl https://mi…...
No.4 笔记 | 探索网络安全:揭开Web世界的隐秘防线
在这个数字时代,网络安全无处不在。了解Web安全的基本知识,不仅能保护我们自己,也能帮助我们在技术上更进一步。让我们一起深入探索Web安全的世界,掌握那些必备的安全知识! 1. 客户端与WEB应用安全 前端漏洞࿱…...
spring揭秘24-springmvc02-5个重要组件
文章目录 【README】【1】HanderMapping-处理器映射容器【1.1】HanderMapping实现类【1.1.1】SimpleUrlHandlerMapping 【2】Controller(二级控制器)【2.1】AbstractController抽象控制器(控制器基类) 【3】ModelAndView(模型与视…...
关键字:register
1.铺垫 1.1 计算集中具有存储能力的硬件:cpu中的寄存器、cache,内存,硬盘等 1.2离cpu越近的存储硬件,效率越高,单价成本越贵;离cpu越远的存储硬件,效率越低,单价成本越便宜&#x…...
力扣 简单 110.平衡二叉树
文章目录 题目介绍解法 题目介绍 解法 平衡二叉树:任意节点的左子树和右子树的高度之差的绝对值不超过 1 //利用递归方法自顶向下判断以每个节点为根节点的左右子树的最大深度是否大于1 class Solution {public boolean isBalanced(TreeNode root) {if(root null){return tr…...
基于深度学习的代码优化
基于深度学习的代码优化是一种使用深度学习技术来提升编程代码性能、减少运行时间或资源消耗的方式。通过模型学习大量代码的特征和结构,深度学习可以帮助自动化地识别和应用优化策略。以下是一些关键应用领域: 编译器优化:深度学习模型可以用…...
汽车电气系统中KL30、KL15、KL50、KLR、KL31、KL87、KL75的作用
目录 1、KL30 (Battery Positive Terminal) 2、KL15 (Ignition Switch, Positive) 3、KL50 (Starter Motor Terminal) 4、KLR (Ignition-Off Draw) 5、KL31 (Ground) 6、KL87 (Relay Output) 7、KL75 (Accessory) 在汽车电气系统中,KL系列的术语起源于德国&a…...
随笔(四)——代码优化
文章目录 前言1.原本代码2.新增逻辑3.优化逻辑 前言 原逻辑:后端data数据中返回数组,数组中有两个对象,一个是属性指标,一个是应用指标,根据这两个指标展示不同的多选框 1.原本代码 getIndicatorRange(indexReportLi…...
安装管理K8S的开源项目KubeClipper介绍
安装管理K8S的开源项目KubeClipper介绍 1. 概述 KubeClipper是九州云开源的一个图形化界面 Kubernetes 多集群管理工具,旨在提供易使用、易运维、极轻量、生产级的 Kubernetes 多集群全生命周期管理服务。让运维工程师从繁复的配置和晦涩的命令行中解放出来&#…...
北交大研究突破:塑料光纤赋能低成本无摄像头AR/VR眼动追踪技术
北交大研究:探索无摄像头低成本AR/VR眼动追踪新路径 在AR/VR技术领域,眼动追踪作为一项关键技术,对于提升用户体验、优化渲染效率具有重要意义。然而,传统的眼动追踪方案多依赖于高成本的摄像头,这不仅增加了设备的制造…...
算法题总结(七)——哈希表
当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法 242、有效地字母异位词 给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。 注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t…...
PS批量执行动作,ps批量修改图片大小,并修改文件的类型
PS批量执行动作,ps批量修改图片大小,并修改文件的类型 修改格式,文件类型为:jpg,psd,tiff,并修改大小 打开文件(也可以不打开,) 点击文件>脚本>文件…...
CentOS 替换 yum源 经验分享
视频教程在bilibili:CentOS 替换 yum源 经验分享_哔哩哔哩_bilibili问题原因 解决方法 1. 进入镜像目录 [rootlocalhost ~]# cd /etc/yum.repos.d/ 2.备份文件 [rootlocalhost yum.repos.d]# rename repo bak * 3.寻找阿里镜像源复制 https://developer.aliyun.com/mirror/ …...
Elasticsearch基础_2.数据类型
文章目录 一、基本的数据类型1.1、keyword1.2、text1.3、数值类型1.4、布尔类型1.5、时间类型 二、复杂的数据类型三、字段映射 一、基本的数据类型 1.1、keyword keyword类型是不进行切分的字符串类型。这里的“不进行切分”指的是:在索引时,对keyword…...
docker快速安装ELK
一、创建elk目录 创建/elk/elasticsearch/data/目录 mkdir -p /usr/local/share/elk/elasticsearch/data/ 创建/elk/logstash/pipeline/目录 mkdir -p /usr/local/share/elk/logstash/pipeline/ 创建/elk/kibana/conf/目录 mkdir -p /usr/local/share/elk/kibana/conf/ 二、创建…...
GS-SLAM论文阅读笔记-CaRtGS
前言 这篇文章看起来有点像Photo-slam的续作,行文格式和图片类型很接近,而且貌似是出自同一所学校的,所以推测可能是Photo-slam的优化与改进方法,接下来具体看看改进了哪些地方。 文章目录 前言1.背景介绍GS-SLAM方法总结 2.关键…...
15分钟学 Python 第36天 :Python 爬虫入门(二)
Python 爬虫入门:环境准备 在进行Python爬虫的学习和实践之前,首先需要准备好合适的开发环境。本节将详细介绍Python环境的安装、必要库的配置、以及常用工具的使用,为后续的爬虫编写奠定坚实的基础。 1. 环境准备概述 1.1 为什么环境准备…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...
centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...
el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
快速排序算法改进:随机快排-荷兰国旗划分详解
随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...
yaml读取写入常见错误 (‘cannot represent an object‘, 117)
错误一:yaml.representer.RepresenterError: (‘cannot represent an object’, 117) 出现这个问题一直没找到原因,后面把yaml.safe_dump直接替换成yaml.dump,确实能保存,但出现乱码: 放弃yaml.dump,又切…...
HTML中各种标签的作用
一、HTML文件主要标签结构及说明 1. <!DOCTYPE html> 作用:声明文档类型,告知浏览器这是 HTML5 文档。 必须:是。 2. <html lang“zh”>. </html> 作用:包裹整个网页内容,lang"z…...
npm安装electron下载太慢,导致报错
npm安装electron下载太慢,导致报错 背景 想学习electron框架做个桌面应用,卡在了安装依赖(无语了)。。。一开始以为node版本或者npm版本太低问题,调整版本后还是报错。偶尔执行install命令后,可以开始下载…...
