拓扑序
1、在做DAG DP时,按拓扑序转移,状态可转移完全
2、从拓扑序小的点连向拓扑序大的点,一定不会成环
3、统计结点\(x\)可以到达的点数(待解决)
Directing Edges
根据性质2,对有向边构成的图跑拓扑,拓扑序小的连向大的即可
正确性由性质2易知,待证明
P3953 [NOIP2017 提高组] 逛公园
本质在做DAG计数DP,按层转移即可
出入度
判断关键点
即删去后使图不连通的点
分析可知,当点\(i\)存在一条出边,它连的点只有这一条入边(入度为1),点\(i\)为关键点
拓扑序判图
一个图中任意两点\(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