首页 > 编程语言 >算法-图论-拓扑排序

算法-图论-拓扑排序

时间:2024-11-03 11:59:05浏览次数:3  
标签:__ node 图论 拓扑 num que result inDegrees 排序

1. 拓扑排序(卡码网 117)

from collections import deque, defaultdict

def main():
    num_node, num_edge = map(int, input().split())
    inDegrees = [0 for _ in range(num_node)]
    edges = defaultdict(list)
    for _ in range(num_edge):
        source, target = map(int, input().split())
        inDegrees[target] += 1
        edges[source].append(target)
    
    # 将入度为0的顶点入度
    que = deque([i for i in range(num_node) if inDegrees[i] == 0])
    result = []
    
    while que:
        cur = que.popleft()
        result.append(cur)
        for t in edges[cur]:
            inDegrees[t] -= 1
            if inDegrees[t] == 0:
                que.append(t)
    
    if len(result) == num_node:
        print(" ".join(map(str, result)))
    else:
        print(-1)
    
    
if __name__ == "__main__":
    main()

标签:__,node,图论,拓扑,num,que,result,inDegrees,排序
From: https://www.cnblogs.com/hifrank/p/18523107

相关文章

  • 【LeetCode:153. 寻找旋转排序数组中的最小值 + 二分】
    在这里插入代码片......
  • 34. 在排序数组中查找元素的第一个位置和最后一个位置
    题目参考了y总讲的这题789.数的范围自己是这样写的;classSolution{public:vector<int>searchRange(vector<int>&nums,inttarget){vector<int>result(2,-1);intl=0,r=nums.size()-1;while(l<r){......
  • 【排序算法】堆排序
    ......
  • 图论基础
    图论基础图的存储图的遍历最小生成树kruskal算法prim算法最短路Dijkstra算法Bellman-Ford算法SPFA算法Floyd-Warshall算法图论基础拓扑排序一笔画问题关键路径差分约束基环树DAG边集数组采用结构体存储边,包括边的起点、终点、权值等信息,这个结......
  • 【排序算法】堆排序
    堆排序堆的认识1、什么是堆在堆排序中,堆是一种特殊的二叉树,它满足以下两个条件一颗完全二叉树,按照整体从上到下,同一层从左到右的顺序排列,不包括平衡树。当父节点的值≥左右孩子的值,根节点的值为最大值时称为大根堆或大顶堆,反之称为小根堆(小顶堆)。2、堆的性质堆的存储......
  • c语言的一些排序算法
    文章目录前言一、......
  • 排序算法:从原理到 Java 实现
    文章目录排序算法:从原理到Java实现一、引言二、常见排序算法原理及Java实现(一)冒泡排序(BubbleSort)(二)选择排序(SelectionSort)(三)插入排序(InsertionSort)(四)快速排序(QuickSort)(五)归并排序(MergeSort)(六)堆排序(HeapSort)三、性能比较与分析(一)时间复杂度(二)空间复杂度(三)稳定......
  • HyperWorks二维网格划分及拓扑改进
    Step01:载入模型Exercise_3a.hm。Step02:2D网格划分。(1) 进入automesh面板。图3-13设置automesh面板网格控制参数 (2)指定elementsize为5,根据图3-13设置网格控制参数。(3)查看网格。图3-14新创建的网格模型 网格模型整体看来比较理想,但局部放大......