18734 拓扑排序

### 思路

1. **建模问题**:将课程和依赖关系建模为有向图,其中课程是节点,依赖关系是有向边。
2. **选择算法**:使用拓扑排序算法来确定课程的学习顺序。由于需要确保输出唯一性,同等条件下编号小的课程排在前面,可以使用优先队列(最小堆)来实现。
3. **初始化**:创建一个入度数组来记录每个节点的入度,并创建一个优先队列来存储入度为0的节点。
4. **更新节点**:从优先队列中取出当前入度为0的节点,将其加入结果序列,并更新其邻接节点的入度。如果邻接节点的入度变为0,将其加入优先队列。
5. **终止条件**:当优先队列为空时,输出结果序列。

### 伪代码

```
function topological_sort(n, m, edges):
    create an array in_degree of size n+1, initialized to 0
    create a graph as an adjacency list of size n+1
    create a priority queue pq
    create a list result

    for each (a, b) in edges:
        graph[a].append(b)
        in_degree[b] += 1

    for i from 1 to n:
        if in_degree[i] == 0:
            pq.push(i)

    while pq is not empty:
        u = pq.pop()
        result.append(u)
        for each v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                pq.push(v)

    return result
```

### C++代码

#include <iostream>
#include <vector>
#include <queue>using namespace std;vector<int> topological_sort(int n, int m, vector<pair<int, int>>& edges) {vector<int> in_degree(n + 1, 0);vector<vector<int>> graph(n + 1);priority_queue<int, vector<int>, greater<int>> pq;vector<int> result;for (const auto& edge : edges) {int a = edge.first;int b = edge.second;graph[a].push_back(b);in_degree[b] += 1;}for (int i = 1; i <= n; ++i) {if (in_degree[i] == 0) {pq.push(i);}}while (!pq.empty()) {int u = pq.top();pq.pop();result.push_back(u);for (int v : graph[u]) {in_degree[v] -= 1;if (in_degree[v] == 0) {pq.push(v);}}}return result;
}int main() {int n, m;cin >> n >> m;vector<pair<int, int>> edges(m);for (int i = 0; i < m; ++i) {int a, b;cin >> a >> b;edges[i] = {a, b};}vector<int> result = topological_sort(n, m, edges);for (int course : result) {cout << course << " ";}cout << endl;return 0;
}

### 总结

1. **问题建模**:将课程和依赖关系建模为有向图,使用拓扑排序算法求解课程学习顺序。
2. **算法选择**:使用拓扑排序算法,利用优先队列(最小堆)确保输出唯一性。
3. **实现细节**:初始化入度数组和优先队列,逐步更新节点的入度并维护优先队列。
4. **终止条件**:当优先队列为空时,输出结果序列。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

fastAPI教程:路由操作及HTTP请求响应

FastAPI 三、路由操作 3.1 路由装饰器 路由装饰器&#xff0c;也叫路径操作装饰器。 FastAPI提供了一系列基于HTTP请求作为方法名的装饰器给开发者用于绑定url地址提供给外界操作API接口。 HTTP方法FastAPI代码描述GETapp.get()async 方法名(): pass获取数据POSTapp.post(…

吴恩达深度学习笔记:卷积神经网络(Foundations of Convolutional Neural Networks)2.5-2.6

目录 第四门课 卷积神经网络&#xff08;Convolutional Neural Networks&#xff09;第二周 深度卷积网络&#xff1a;实例探究&#xff08;Deep convolutional models: case studies&#xff09;2.5 网络中的网络以及 11 卷积&#xff08;Network in Network and 11 convoluti…

【AI知识点】批归一化(Batch Normalization)

批归一化&#xff08;Batch Normalization&#xff0c;BN&#xff09; 是一种用于加速神经网络训练并提高模型稳定性的方法&#xff0c;最早由 Sergey Ioffe 和 Christian Szegedy 在 2015 年提出。批归一化通过在每一层对神经网络中的激活值进行标准化&#xff0c;使得每一层的…

D29【python 接口自动化学习】- python基础之输入输出与文件操作

day29 格式化输出 学习日期&#xff1a;20241006 学习目标&#xff1a;输入输出与文件操作&#xfe63;-41 格式化输出&#xff1a;如何将执行结果通过屏幕输出&#xff1f; 学习笔记&#xff1a; 三种常用的格式化输出方式 百分号方式 format函数方式 总结 1. 格式化输出…

在ubuntu好部署jenkins发布vue项目时遇到的一些问题及解决方法以及使用jenkins发布vue项目-npm自动打包发布的实现

一、在ubuntu好部署jenkins发布vue项目时遇到的一些问题及解决方法 1. 问题&#xff1a;webpack-dev-server不是内部或外部命令&#xff0c;也不是可运行的程序 解决&#xff1a;使用webpack要安装webpack-cli这个包&#xff0c;才可以调用webpack和webpack-dev-server这些命…

Hive3.x版本调优总结

文章目录 第 1 章 Explain 查看执行计划&#xff08;重点&#xff09;1.1 创建测试用表1&#xff09;建大表、小表和 JOIN 后表的语句2&#xff09;分别向大表和小表中导入数据 1.2 基本语法1.3 案例实操 第 2 章 Hive 建表优化2.1 分区表2.1.1 分区表基本操作2.1.2 二级分区2.…

虚拟机 VMware 安装 macOS

macOS 界面 MAC OS IOS下载&#xff1a; amacOS Monterey by Techrechard.comwmacOS Monterey by Techrechard.com 下载&#xff1a;Unlocker-v2.0.1-x64 Mac OS X 虚拟机中更改屏幕分辨率 终端输入命令&#xff1a; sudo defaults write /Library/Preferences/com.apple.w…

2-114 基于matlab的CA模型

基于matlab的CA模型&#xff0c;Singer模型对单机动目标进行跟踪算法&#xff0c;具有10页实验文档。采用蒙特卡罗方法对一个二坐标雷达对一平面上运动的目标进行观测&#xff0c;得到跟踪滤波结果。程序已调通&#xff0c;可直接运行。 下载源程序请点链接&#xff1a;2-114 …

Linux:进程的创建、终止和等待

一、进程创建 1.1 fork函数初识 #include pid_t fork(void); 返回值&#xff1a;子进程中返回0&#xff0c;父进程返回子进程id&#xff0c;出错返回-1 调用fork函数后&#xff0c;内核做了下面的工作&#xff1a; 1、创建了一个子进程的PCB结构体、并拷贝一份相同的进程地址…

Stable Diffusion绘画 | IP角色多视图生成技巧

在游戏设计、小说推文、角色设计里面&#xff0c;很多场景都运用到IP角色的多视图。 人物角色多视图 第1步&#xff0c;输入提示词&#xff1a; 第2步&#xff0c;由于要在同一张图片中生成多角度的并排展示&#xff0c;需要修改图片的分辨率&#xff08;尤其是宽度&#xff…

Pytorch实现心跳信号分类识别(支持LSTM,GRU,TCN模型)

Pytorch实现心跳信号分类识别(支持LSTM,GRU,TCN模型&#xff09; 目录 Pytorch实现心跳信号分类识别(支持LSTM,GRU,TCN模型&#xff09; 1. 项目说明 2. 数据说明 &#xff08;1&#xff09;心跳信号分类预测数据集 3. 模型训练 &#xff08;1&#xff09;项目安装 &am…

MoveIt2-humble----在 RViz 中实现可视化

官方文档上的教程&#xff0c;从moveit1的melodic到moveit2的foxy基本一致&#xff0c;但是从最新的humble开始有了很大的变化&#xff0c;其中之一便是 lambda表达式 的广泛使用。 本节为教程的第二节&#xff0c;会介绍一个工具&#xff08;moveit_visual_tools&#xff09;…

运动员场景分割系统源码&数据集分享

运动员场景分割系统源码&#xff06;数据集分享 [yolov8-seg-HGNetV2&#xff06;yolov8-seg-aux等50全套改进创新点发刊_一键训练教程_Web前端展示] 1.研究背景与意义 项目参考ILSVRC ImageNet Large Scale Visual Recognition Challenge 项目来源AAAI Global Al lnnovati…

麒麟 操作系统介绍| 银河麒麟和中标麒麟操作系统| Kylin 麒麟iso 镜像下载地址 银河麒麟操作系统v10 |

目录 #申请试用小技巧&#xff0c; 所有麒麟系列的版本如下 详细介绍如下&#xff1a; 银河麒麟高级服务器操作系统 V10 1. 龙芯-MIPS64el 版 2. 申威版 3. 兆芯版 4. 海光版 5. 飞腾版 6. 鲲鹏版 7. AMD64版 8. 龙芯-LoongArch64 版 9. ARM64版 银河麒麟桌面操作…

SpringMVC源码-AbstractUrlHandlerMapping处理器映射器将实现Controller接口的方式定义的路径存储进去

DispatcherServlet的initStrategies方法用来初始化SpringMVC的九大内置组件 initStrategies protected void initStrategies(ApplicationContext context) {// 初始化 MultipartResolver:主要用来处理文件上传.如果定义过当前类型的bean对象&#xff0c;那么直接获取&#xff0…

【学习笔记】kruskal重构树

前言 最近一场div2没开出C2&#xff0c;猛掉104分。 赛后补E&#xff0c;发现自己连E1都没思路&#xff0c;一问才知道是kruskal重构树。 好吧&#xff0c;OI时期欠下的债该还了。 kruskal重构树是什么 它是一棵 2 n − 1 2n-1 2n−1 个点的二叉树。点有点权&#xff0c;下…

异常场景分析

优质博文&#xff1a;IT-BLOG-CN 为了防止黑客从前台异常信息&#xff0c;对系统进行攻击。同时&#xff0c;为了提高用户体验&#xff0c;我们都会都抛出的异常进行拦截处理。 一、异常处理类 Java把异常当做是破坏正常流程的一个事件&#xff0c;当事件发生后&#xff0c;…

https访问报错:net::ERR_CERT_DATE_INVALLD

目录 简介异常排查原因解决补充 简介 访问https资源出现报错 异常 排查 将地址拿到浏览器进行访问&#xff0c;可以很清晰的看到出现该问题的原因 原因 1、SSL证书已过期 2、服务器日期不准&#xff0c;不在证书有效期 解决 1、重新申请SSL证书&#xff0c;并配置 2、校正…

VMware桥接模式无法连接网络

windows下打开控制面板&#xff0c;找到WLAN&#xff0c;记住下面的名称&#xff08;带有VMware的都是虚拟机的网卡&#xff0c;要找到物理主机的网卡&#xff09; 回到VMware&#xff0c;编辑——打开虚拟网络编辑器 桥接选择上面的WLAN下的网络名称&#xff0c;确定即可。&…

【学习笔记】手写一个简单的 Spring MVC

目录 一、什么是Spring MVC &#xff1f; Spring 和 Spring MVC 的区别&#xff1f; Spring MVC 的运行流程&#xff1f; 二、实现步骤 1. DispatcherServlet 1. 创建一个中央分发器 拦截所有请求 测试 2. 接管 IOC 容器 1. 创建配置文件 2. 修改 web.xml 配置文件 …