拓扑排序基操

拓扑排序也算是图论的一部分，主要是解决有向无环图的问题。

在算阶上的板子如下

void add(int x,int y){v[++tot]=y;nxt[tot]=head[x];head[x]=tot;deg[y]++;}
void topsort()
{queue<int> q;for(int i=1;i<=n;i++)if(deg[i]==0){q.push(i);}while(q.size()){int x=q.front();q.pop();for(int i=head[x];i;i=nxt[i]){int y=v[i];if(--deg[y]==0) q.push(y);}}
}

（码风丑陋是因为我压行了）

void add(int x,int y){v[++tot]=y;nxt[tot]=head[x];head[x]=tot;deg[y]++;}

这一部分不用说，是在邻接表中添加一个有向边。

像这样一个图，我们首先让入度为$0$的$1，3，6，7$入队
然后将$1$中的东西上传到$2$上，$3$上的东西上传到$2$上，此时

$2$的入度为$0$，所以也进入队列里，而$1$的出度为$0$，所以出队，队列变为$3，6，7，2$
然后将$3$上传到$4$，$4$的入度减减，$3$的出度为$0$，出队
以此类推，直到队列里面什么也没有

直接上一道例题吧

题目描述

小W在上数理逻辑的课。他想要自创一套公理系统。

现在小W有 $n$ 个命题，标号为 $1-n$，他有 $m$ 个推出关系。每个推出关系都是形如 $P\Rightarrow Q$，意思是如果 $P$ 被证明是对的，那么就可以推出 $Q$ 是对的。你可以把这些推出关系想成一个有向图。他发现这张图没有环。他现在想要从中选出一些命题设为公理，要求其它所有命题都可以通过这些公理推出。他想要最小化选出的公理数，并输出任意一种方案即可。

小W给出公理之后，小W的朋友小Y想要通过这些公理去证明所有命题。对于每一个命题 $T$，他想要用最少的推导次数证明这个命题。即找一条路径 v 1 , v 2 , … , v k = T v_1,v_2,\dots,v_k=T v1​,v2​,…,vk​=T，满足 v 1 v_1 v1​ 是一条公理，并且 ∀   i ∈ [ 1 , k − 1 ] ,   v i ⇒ v i + 1 \forall\ i \in [1,k-1],\ v_i \Rightarrow v_{i+1} ∀ i∈[1,k−1], vi​⇒vi+1​，则推导次数是 $k-1$。

输入格式

第一行两个整数 $n,m$。
接下来 $m$ 行，每行两个整数 $P,Q$，表示第 $P$ 个命题可以推出第 $Q$ 个命题。

输出格式

第一行一个整数 $k$，表示公理的个数。
第二行 $k$ 个整数，表示选出的公理，按从小到大输出。
第三行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个命题的最少推导次数。

样例数据

input

7 6
1 3
2 3
3 4
3 5
4 6
5 6

output

3
1 2 7
0 0 1 2 2 3 0

数据规模与约定

对于 $20\%$ 的数据，$n,m\le 15$。
对于 $60\%$ 的数据，$n,$

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！