OD C卷 - 查找一个有向网络的头节点和尾节点

查找一个有向网络的头节点和尾节点 (200)

  • 在一个有向图中,有向边用两个整数表示,第一个整数表示起始节点,第二个整数表示终止节点;
  • 图中只有一个头节点,一个或者多个尾节点;
  • 图可能存在环,有环则输出-1;
  • 输出图中的头节点(入度为0)、尾节点(出度为0),如图头节点为1,尾节点为4。
    在这里插入图片描述
    输入描述:
    第一行输入n,n >=0
    第二行为n个数对,表示n条边;
    输出描述:
    输出一行,头节点、尾节点以空格隔开,多个尾节点则从大到小输出。
     
    示例1
    输入:
    4
    1 2 1 3 2 4 3 4
    输出:
    1 4
     
    示例2
    输入:
    3
    1 2 1 3 1 4
    输出:
    1 4 3 2
     
    示例3
    输入:
    4
    1 2 2 3 3 4 4 1
    输出:
    -1
     
    示例4
    输入:
    5
    1 2 2 3 3 4 4 5 4 2
    输出:
    -1
    思路:
  • 拓扑排序,判断有向图是否有环,有环则直接输出-1;
  • 只有一个起始点,一个或多个结尾点;
# __author__ = "laufing"class GraphHeadTail:def solution(self, n, edges):# 所有的顶点和数目vertex = list(set(edges))vertex_num = len(vertex)# 统计每个顶点的入度in_degree = {}.fromkeys(vertex, 0)# 每个顶点的出度out_degree = {}.fromkeys(vertex, 0)for i in range(n):u, v = edges[i*2:(i+1)*2]out_degree[u] += 1in_degree[v] += 1# 找到入度为零的一个节点start_node = Nonefor key in in_degree:if in_degree.get(key) == 0:start_node = keybreakif self.topology_sort(in_degree, start_node, edges, vertex_num):print(-1)return -1# 无环  输出头节点 + 尾节点# 找到所有的尾节点tails = []for key in out_degree:if out_degree.get(key) == 0:tails.append(key)tails.sort(reverse=True)result = str(start_node) + " " + " ".join(list(map(str, tails)))print(result)return resultdef topology_sort(self, in_degree, start_node, edges, vertex_num):in_degree = in_degree.copy() # 不影响原始数据if start_node is None:return Truestack = []output_list = []stack.append(start_node)while stack:nodev = stack.pop()print("nodev:", nodev)output_list.append(nodev)# 删除边,对应的顶点入度-1for i in range(len(edges) // 2):u, v = edges[i*2:(i+1)*2]if u == nodev:in_degree[v] -= 1if in_degree[v] == 0:stack.append(v)print(output_list)return len(output_list) < vertex_numif __name__ == '__main__':graph_head_tail = GraphHeadTail()while True:try:n = int(input("n:").strip())edges = list(map(int, input("edges:").strip().split()))graph_head_tail.solution(n, edges)except KeyboardInterrupt:break

 

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

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

相关文章

RTX 40全系10款显卡《黑神化:悟空》测试:打开DLSS3帧生成 性能直翻4倍

一、前言&#xff1a;《黑神话&#xff1a;悟空》临近发布 RTX 40系显卡表现如何&#xff1f; 2020年8月20日&#xff0c;游戏科学发布了《黑神话&#xff1a;悟空》的首个实机演示预告&#xff0c;惊艳了整个游戏行业&#xff01; 以往&#xff0c;很多人认为国产开发商做不出…

华为数通方向HCIP-DataCom H12-821题库(更新单选真题:1-10)

第1题 1、下面是一台路由器的部分配置,关于该配置描述正确的是? [HUAWEllact number 2001 [HUAWEl-acl-basic-2001]rule 0 permit source 1.1.1.1 0 [HUAWEl-acl-basic-2001]rule 1 deny source 1.1.1.0 0 [HUAWEl-acl-basic-2001]rule

Java实现STL中的全排列函数next_permutation()

目录 一、引言 二、全排列函数next_permutation() 三、next_permutation()的使用 四、Java实现next_permutation() 五、使用next_permutation()实现全排列 一、引言 相信很多小伙伴们都做过全排列的算法题&#xff0c;输入一个n&#xff0c;输出1~n的全排列。对于这个问题…

jemeter压力测试入门

1. 安装jemeter的压缩包并且解压 点击运行 2. 添加线程组 3. 线程组的参数设置 4. 添加http请求 5. 填写请求信息 添加监听器——结果树&#xff08;结果&#xff09;&#xff0c;聚合报告&#xff08;吞吐量报告&#xff09; 6. 通过cvs数据文件设置&#xff0c;配置元件&…

ARM 裸机与 Linux 驱动对比及 Linux 内核入门

目录 ARM裸机代码和驱动的区别 Linux系统组成 内核五大功能 设备驱动分类 内核类型 驱动模块 驱动模块示例 Makefile配置 命令 编码辅助工具 内核中的打印函数 printk 函数 修改打印级别 ​编辑 打印级别含义 驱动多文件编译 示例 模块传递参数 命令行传递参数…

jmeter简单发送接口

一、安装jmeter 拥有java环境&#xff0c;再下载jmeter 安装之后解压到本地&#xff0c;jmeter中的bin目录配置到环境变量中 之后可以通过cmd中 jmeter.bat命令运行 二、利用jmeter发送接口请求 1、添加线程组 添加->线程->线程组 2、添加http请求 添加->取样器-&g…

利用Matlab求解高阶微分方程(ode45)

1、高阶微分方程的基本概念 二阶以及二阶以上的微分方程称之为高阶微分方程&#xff0c;一般来说&#xff0c;微分方程的阶数越高&#xff0c;求解的难度也就越大。求高阶方程的一个常用方法就是降低阶数。对二阶方程 &#xff0c;如果能用变量代换把它化成一阶方程&#xff0c…

学习记录——day33 HTTP

目录 一、HTTP相关概念 二、客服端请求 1、请求首部 2、 响应首部 三、线程实现HTTP并发服务器 一、HTTP相关概念 1、HTTP&#xff0c;全称Hyper Text Transfer Protocol&#xff0c;用于万维网&#xff08;world wide web&#xff09;进行超文本学习的传输协议 2、HTTP属…

计算xpclr

1.conda安装xpclr 首先安装流程很轻松 conda create -n xpclr -c bioconda xpclr conda activate xpclr xpclr -h 2.按照要求准备文件 XPCLR - 简书 (jianshu.com) 根据教程准备文件&#xff0c;vcf&#xff0c;计算好的map&#xff0c;以及样本文件txt 其实官网也有介绍…

Docker基础概述、Docker安装、Docker镜像加速、Docker镜像指令

1.为什么学docker 开发环境与测试环境不同&#xff0c;导致错误 因此docker提供解决方法———系统平滑移植&#xff0c;容器虚拟化技术 将代码与软件与配置文件 打包成一个镜像 2.docker的历练 创建一个开发环境内成为镜像文件再用docker使用镜像 3.什么是docker Docke…

MySQL5.7数据库---入门教程(小白教程)

一、MySQL安装 本文以MySQL5.7安装为例。在设置完root密码和添加一个用户后&#xff0c;一路默认。 1、 2、通过点击红圈里的箭头选择对应的版本。 3、 4、端口&#xff08;Port&#xff09;一般默认不需要更改。 5、 二、配置环境变量 配置环境变量可以方便在win系统中cmd…

流媒体服务器二 3学习 librtmp 库的配置使用

librtmp 库是个啥&#xff1f; librtmp是一个开源的基于C语言的库&#xff0c;提供了一个连接RTMP服务器&#xff0c;发送和接收RTMP流的API。 它可以用来开发流媒体播放器&#xff0c;网络直播等应用。它的主要特点是快速、稳定和低延迟。 librtmp支持RTMP&#xff0c;RTMPS…

Qt第十七章 多线程

文章目录 多线程1. 线程概念的起源2. 三种方式创建线程3. 启动线程前的准备工作4. 启动线程/退出线程5. 操作运行中的线程6. 为每个线程提供独立数据7.子线程不能操作ui解决方案 多线程 1. 线程概念的起源 单核CPU 早期还没有线程的概念&#xff0c;如何保证2个进程同时进行呢…

基于Java爬取微博数据(四) 获取 图片 or 视频

基于Java爬取微博数据四 获取 图片 or 视频 图片 or 视频转存 图片 or 视频注意点 前面已经讲述了基于 Java 爬取微博正文列表内容&#xff0c;微博用户主页内容以及导出爬取到的微博数据等操作&#xff0c;那么下面讲述一下如何处理微博正文中的图片/视频等内容。 图片 or 视…

(转载)使用zed相机录制视频

参照下面这个链接 https://blog.csdn.net/peng_258/article/details/127457199?ops_request_misc&request_id&biz_id102&utm_termzed2%E5%BD%95%E5%88%B6%E6%95%B0%E6%8D%AE%E9%9B%86&utm_mediumdistribute.pc_search_result.none-task-blog-2~all~sobaiduweb…

代码复现改进

代码复现&#xff0c;文献复现&#xff0c;文章复现&#xff0c; 算法复现&#xff0c;科研复现 Matlab,Python中英文均可 保证质量&#xff0c;加快你的研究速度 代码改进跑通&#xff0c;模型优化改进

三种相机模型总结(针孔、鱼眼、全景)

相机标定 文章目录 相机标定前言 前言 我们最常见的投影模型Perspective Projection Model描述的就是针孔相机的成像原理。从上面的图根据相似三角形可以得出 参考链接 https://zhuanlan.zhihu.com/p/540969207 相机标定之张正友标定法数学原理详解&#xff08;含python源码&a…

鹭鹰优化算法SBOA优化RBF神经网络的扩散速度实现多数入多输出数据预测,可以更改数据集(MATLAB代码)

一、鹭鹰优化算法介绍 鹭鹰优化算法&#xff08;Secretary Bird Optimization Algorithm, SBOA&#xff09;是一种新型的元启发式算法&#xff0c;它于2024年4月由Youfa Fu等人提出&#xff0c;并发表在SCI人工智能二区顶刊《Artificial Intelligence Review》上。该算法的灵感…

uniapp h5手机如何打开本地跑的前端项目进行本地调试

本地调试使用 vConsole是一个轻量级的移动端调试工具&#xff0c;可以在iOS设备上直接调试Uniapp H5应用。下面是具体的步骤&#xff1a; 在Uniapp项目中安装vConsole依赖&#xff1a;npm install vconsole。 在项目的main.js文件中引入vConsole库&#xff1a;import VConso…

将iso格式的镜像文件转化成云平台能安装的镜像格式(raw/vhd/QCOW2/VMDK )亲测--图文详解

1.首先,你将你的iso的文件按照正常的流程和需求安装到你的虚拟机中,我这里使用的是vmware,安装完成之后,关机。再次点开你安装好的那台虚拟机的窗口,如下图 选中要导出的镜像,镜像需要关机 2.点击工具栏的文件------选择 导出 整个工程到 ovf 格式—这里你可以选择你要导…