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

卡码网KamaCoder 117. 软件构建

题目来源:117. 软件构建

C++题解(来源代码随想录):拓扑排序:给出一个 有向图,把这个有向图转成线性的排序。拓扑排序也是图论中判断有向无环图的常用方法

拓扑排序的过程,其实就两步:

  1. 找到入度为0 的节点,加入结果集
  2. 将该节点从图中移除

循环以上两步,直到 所有节点都在图中被移除了。

#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. 软件构建

题目来源&#xff1a;117. 软件构建 C题解&#xff08;来源代码随想录&#xff09;&#xff1a;拓扑排序&#xff1a;给出一个 有向图&#xff0c;把这个有向图转成线性的排序。拓扑排序也是图论中判断有向无环图的常用方法。 拓扑排序的过程&#xff0c;其实就两步&#xff1…...

Acwing 线性DP

状态转移方程呈现出一种线性的递推形式的DP&#xff0c;我们将其称为线性DP。 Acwing 898.数字三角形 实现思路&#xff1a; 对这个三角形的数字进行编号&#xff0c;状态表示依然可以用二维表示&#xff0c;即f(i,j),i表示横坐标&#xff08;横线&#xff09;&#xff0c;j表…...

Docker面试-24年

1、Docker 是什么&#xff1f; Docker一个开源的应用容器引擎&#xff0c;是实现容器技术的一种工具&#xff0c;让开发者可以打包他们的应用以及环境到一个镜像中&#xff0c;可以快速的发布到任何流行的操作系统上。 2、Docker的三大核心是什么? 镜像&#xff1a;Docker的…...

ubuntu 安装k8s

#关闭 Swap 内存&#xff0c;配置完成建议重启一下 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世界的隐秘防线

在这个数字时代&#xff0c;网络安全无处不在。了解Web安全的基本知识&#xff0c;不仅能保护我们自己&#xff0c;也能帮助我们在技术上更进一步。让我们一起深入探索Web安全的世界&#xff0c;掌握那些必备的安全知识&#xff01; 1. 客户端与WEB应用安全 前端漏洞&#xff1…...

spring揭秘24-springmvc02-5个重要组件

文章目录 【README】【1】HanderMapping-处理器映射容器【1.1】HanderMapping实现类【1.1.1】SimpleUrlHandlerMapping 【2】Controller&#xff08;二级控制器&#xff09;【2.1】AbstractController抽象控制器&#xff08;控制器基类&#xff09; 【3】ModelAndView(模型与视…...

关键字:register

1.铺垫 1.1 计算集中具有存储能力的硬件&#xff1a;cpu中的寄存器、cache&#xff0c;内存&#xff0c;硬盘等 1.2离cpu越近的存储硬件&#xff0c;效率越高&#xff0c;单价成本越贵&#xff1b;离cpu越远的存储硬件&#xff0c;效率越低&#xff0c;单价成本越便宜&#x…...

力扣 简单 110.平衡二叉树

文章目录 题目介绍解法 题目介绍 解法 平衡二叉树:任意节点的左子树和右子树的高度之差的绝对值不超过 1 //利用递归方法自顶向下判断以每个节点为根节点的左右子树的最大深度是否大于1 class Solution {public boolean isBalanced(TreeNode root) {if(root null){return tr…...

基于深度学习的代码优化

基于深度学习的代码优化是一种使用深度学习技术来提升编程代码性能、减少运行时间或资源消耗的方式。通过模型学习大量代码的特征和结构&#xff0c;深度学习可以帮助自动化地识别和应用优化策略。以下是一些关键应用领域&#xff1a; 编译器优化&#xff1a;深度学习模型可以用…...

汽车电气系统中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) 在汽车电气系统中&#xff0c;KL系列的术语起源于德国&a…...

随笔(四)——代码优化

文章目录 前言1.原本代码2.新增逻辑3.优化逻辑 前言 原逻辑&#xff1a;后端data数据中返回数组&#xff0c;数组中有两个对象&#xff0c;一个是属性指标&#xff0c;一个是应用指标&#xff0c;根据这两个指标展示不同的多选框 1.原本代码 getIndicatorRange(indexReportLi…...

安装管理K8S的开源项目KubeClipper介绍

安装管理K8S的开源项目KubeClipper介绍 1. 概述 KubeClipper是九州云开源的一个图形化界面 Kubernetes 多集群管理工具&#xff0c;旨在提供易使用、易运维、极轻量、生产级的 Kubernetes 多集群全生命周期管理服务。让运维工程师从繁复的配置和晦涩的命令行中解放出来&#…...

北交大研究突破:塑料光纤赋能低成本无摄像头AR/VR眼动追踪技术

北交大研究&#xff1a;探索无摄像头低成本AR/VR眼动追踪新路径 在AR/VR技术领域&#xff0c;眼动追踪作为一项关键技术&#xff0c;对于提升用户体验、优化渲染效率具有重要意义。然而&#xff0c;传统的眼动追踪方案多依赖于高成本的摄像头&#xff0c;这不仅增加了设备的制造…...

算法题总结(七)——哈希表

当我们遇到了要快速判断一个元素是否出现集合里的时候&#xff0c;就要考虑哈希法 242、有效地字母异位词 给定两个字符串 s 和 t &#xff0c;编写一个函数来判断 t 是否是 s 的字母异位词。 注意&#xff1a;若 s 和 t 中每个字符出现的次数都相同&#xff0c;则称 s 和 t…...

PS批量执行动作,ps批量修改图片大小,并修改文件的类型

PS批量执行动作&#xff0c;ps批量修改图片大小&#xff0c;并修改文件的类型 修改格式&#xff0c;文件类型为&#xff1a;jpg&#xff0c;psd&#xff0c;tiff&#xff0c;并修改大小 打开文件&#xff08;也可以不打开&#xff0c;&#xff09; 点击文件>脚本>文件…...

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类型是不进行切分的字符串类型。这里的“不进行切分”指的是&#xff1a;在索引时&#xff0c;对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的续作&#xff0c;行文格式和图片类型很接近&#xff0c;而且貌似是出自同一所学校的&#xff0c;所以推测可能是Photo-slam的优化与改进方法&#xff0c;接下来具体看看改进了哪些地方。 文章目录 前言1.背景介绍GS-SLAM方法总结 2.关键…...

15分钟学 Python 第36天 :Python 爬虫入门(二)

Python 爬虫入门&#xff1a;环境准备 在进行Python爬虫的学习和实践之前&#xff0c;首先需要准备好合适的开发环境。本节将详细介绍Python环境的安装、必要库的配置、以及常用工具的使用&#xff0c;为后续的爬虫编写奠定坚实的基础。 1. 环境准备概述 1.1 为什么环境准备…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

GO协程(Goroutine)问题总结

在使用Go语言来编写代码时&#xff0c;遇到的一些问题总结一下 [参考文档]&#xff1a;https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现&#xff1a; 今天在看到这个教程的时候&#xff0c;在自己的电…...

安卓基础(Java 和 Gradle 版本)

1. 设置项目的 JDK 版本 方法1&#xff1a;通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分&#xff0c;设置 Gradle JDK 方法2&#xff1a;通过 Settings File → Settings... (或 CtrlAltS)…...

如何在Windows本机安装Python并确保与Python.NET兼容

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…...

快速排序算法改进:随机快排-荷兰国旗划分详解

随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...