首页 > 其他分享 >拓扑排序

拓扑排序

时间:2024-10-31 17:10:34浏览次数:1  
标签:序小 DAG 拓扑 到达 有环 排序 DP

拓扑序

1、在做DAG DP时,按拓扑序转移,状态可转移完全

2、从拓扑序小的点连向拓扑序大的点,一定不会成环

3、统计结点\(x\)可以到达的点数(待解决)

Directing Edges

根据性质2,对有向边构成的图跑拓扑,拓扑序小的连向大的即可

正确性由性质2易知,待证明

P3953 [NOIP2017 提高组] 逛公园

本质在做DAG计数DP,按层转移即可

出入度

判断关键点

即删去后使图不连通的点

分析可知,当点\(i\)存在一条出边,它连的点只有这一条入边(入度为1),点\(i\)为关键点

例:P1841 [JSOI2007] 重要的城市

拓扑序判图

一个图中任意两点\(x,y\),都有①\(x\)能到达\(y\)、②\(y\)能到达\(x\),只满足一个,判断是否合法

首先有环不合法,因为满足了两个,则剩下DAG

DAG中有两点互不到达的情况,也不合法

则满足条件的是:拓扑序小的一定可以到达拓扑序大的

做法:队列中时刻只有一个数(推导?)

判环

图有环时,\(in[i] \ne 0\),因此不可能进入宽搜队列,因此可以用 \(in[i] \not = 0\) 来判断是否有环。

标签:序小,DAG,拓扑,到达,有环,排序,DP
From: https://www.cnblogs.com/zhone-lb/p/18518390

相关文章

  • Day26--冒泡排序
    Day26--冒泡排序冒泡排序无疑是最为出名的排序算法之一:总共有八大排序!冒泡的代码还是相当简单的,两层循环:外层冒泡轮数,里层依次比较:江湖中人人尽皆知。我们看到嵌套循环:应该立马就可以得出这个算法的时间复杂度为O(n²)。思考:如何优化?1.冒泡排序的思路理解:一、冒泡排序的起......
  • qsort排序
    在体操比赛中,每位选手的得分是由多名裁判综合打分所得。现在已经汇总了N名选手的个人总得分(选手的编号依次为1,2,……N),请你设计程序找出第K名选手在所有选手中的排名。输入说明:第一行是N和K,N表示运动员的个数,K是选手序号;第二行依次是这N位运动员的个人总得分。输出说明:第K名(从1开......
  • xtu oj 逆序数(小数据) //冒泡排序
    题目描述给你一个序列x1,x2,…,xn,如果数对<xi,xj>,其中i<j,而xi>xj我们称之为逆序数对。一个序列的逆序数对的数目,称为这个序列的逆序数。比如说序列312,逆序数对为<3,1>和<3,2>,所以这个序列的逆序数为2。现在给你一个数字序列,请求其逆序数。输入每个样例为两行......
  • 项目进度计划中的任务如何优先排序
    项目进度计划中的任务优先排序取决于多个因素:任务的紧迫性、依赖关系、资源可用性、项目关键路径以及潜在风险。通常,在确定任务优先级时,应首先考虑关键路径上的任务,因为这些任务直接影响项目完成的总时长。接着,考虑那些有着严格截止日期或是对项目成败至关重要的任务。资源的分配......
  • 【数据结构多彩画卷】不要只会普通的二叉树了 , 你听说过用二叉树来排序吗? 【二叉搜索
    本篇会加入个人的所谓鱼式疯言❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言而是理解过并总结出来通俗易懂的大白话,小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的.......
  • 【信奥赛·算法基础】插入排序:算法解析与C++实现
    序言插入排序(InsertionSort)是一种简单的排序算法,就像是我们在打扑克牌时,整理手中牌的过程。一、基本原理插入排序的基本思想是:将待排序的元素插入到已经有序的部分序列中合适的位置,直到所有元素都插入完毕,整个序列就变为有序序列。二、算法步骤从第二个元素开始(假设第......
  • 排序算法在最坏情况下的性能差异:深入分析
    目录1.排序算法简介2.最坏情况示例分析2.1插入排序2.2归并排序2.3快速排序2.4堆排序3.性能差异与优化策略4.拓展知识:算法选择与优化5.结语        在软件工程中,排序算法是数据处理的基石。不同的排序算法在不同情况下表现出不同的性能。本文将通过......
  • 堆排序算法和Topk思想
    目录1>>导言2>>堆排序2.1>>通过堆结构实现堆排序2.2>>堆思想实现排序3>>Topk思想4>>代码5>>结语1>>导言    今天重点内容就是带着大家实现堆排序和Topk,堆排序分为两种,一种是直接调用堆的数据结构来实现的,另一种就是通过堆的思想实现的,Topk就是在一个数组......
  • 冒泡排序的学习与使用
    一.什么是冒泡数列?1.冒泡数列就是元素按ASCII码值从小到大排序的数列,由于很像水中泡泡向上冒出的形态,所以叫冒泡数列,如图:        二.如何将一个数列转换成冒泡数列?     答:使用冒泡排序即可将一个乱序的数列转换成冒泡数列。    冒泡排序即按ASCI......
  • 未排序数组的树层去重
    491.递增子序列reference/*未排序+树层去重之前在进行树层去重时,我们都是先对元素排序,这样如果树层中的元素重复,它们的位置一定是相邻的,因此我们可以通过!st[i-1]来判断树层元素是否重复但现在我们不能对元素进行排序,该如何去重呢?其实也很简单,对于树中的每一层,我们只需......