拓扑排序¶
百科 对一个有向无环图(Directed Acyclic Graph，简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边 \(<u,v>∈E(G)\) ，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。例如，在日常工作中，可能会将项目拆分成A、B、C、D四个子部分来完成，但A依赖于B和D，C依赖于D。为了计算这个项目进行的顺序，可对这个关系集进行拓扑排序，得出一个线性的序列，则排在前面的任务就是需要先完成的任务。 注意：这里得到的排序并不是唯一的！就好像你早上穿衣服可以先穿上衣也可以先穿裤子，只要里面的衣服在外面的衣服之前穿就行。
实现¶
在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：
-
每个顶点出现且只出现一次。
-
若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。 有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。
例如，下面这个图：
它是一个 DAG 图，那么如何写出它的拓扑排序呢？这里说一种比较常用的方法：
从 DAG 图中选择一个 没有前驱（即入度为0）的顶点并输出。 从图中删除该顶点和所有以它为起点的有向边。 重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中**必然存在环**。
于是，得到拓扑排序后的结果是 { 1, 2, 4, 3, 5 }。
通常，一个有向无环图可以有**一个或多个**拓扑排序序列。
void topu(){
for(int i=1;i<=n;i++)if(!in[i])q.push(i);//点的入度
while(q.size()){
int u=q.front();
cout<<u<<' ';//输出topu序
q.pop();
if(vis[u])continue;
vis[u]=1;
for(auto v:e[u]){
if(vis[v])continue;
in[v]--;
if(!in[v])q.push(v);
}
}
}
拓扑排序的应用
拓扑排序通常用来“排序”具有依赖关系的任务。
比如，如果用一个DAG图来表示一个工程，其中每个顶点表示工程中的一个任务，用有向边 表示在做任务 B 之前必须先完成任务 A。故在这个工程中，任意两个任务要么具有确定的先后关系，要么是没有关系，绝对不存在互相矛盾的关系（即环路）。 引用自： https://blog.csdn.net/lisonglisonglisong/article/details/45543451
例题 #1 郁闷的记者¶
你是一个体育报社的记者，你接受到一个艰难的任务：有 \(N\) 支足球队参加足球比赛，现在给你一些比赛的结果，需要你给出各支球队的排名，从 \(1\) 到 \(N\)。
以下是给你的一些信息：
-
没有平局；
-
不同的球队排名不能相同；
-
对于所有满足 \(1 \le a<b \le N\)，第 \(a\) 名的球队一定可以打败第 \(b\) 名的球队。
给你部分比赛结果，要求给出排名，并且判断是否存在另一种排名方法满足给你的比赛结果。
拓扑排序就是一种合法的顺序。
判定多解：在任意时刻，q中的元素都是当前入度=0的点，事实上我们可以从中任意取出一个都是满足要求的。于是只要判定有没有时刻q中元素个数超过1即可。这个性质同样可以被利用来求解字典序最小/大的拓扑序。
vector<int> e[N];
int ind[N];
int vis[N],ans[N],top;
queue<int> q;
void add(int b,int a){
e[a].pb(b);
ind[b]++;
}
signed main(){
int n=rd,m=rd;
for(int i=1;i<=m;i++){
add(rd,rd);
}
for(int i=1;i<=n;i++){
if(!ind[i])q.push(i);
}
int f=0;
while(q.size()){
if(q.size()>1)f=1;
int x=q.front();
ans[++top]=x;
vis[x]=1;
q.pop();
for(auto v:e[x]){
if(!--ind[v])q.push(v);
}
}
for(int i=1;i<=top;i++){
cout<<ans[i]<<endl;
}
for(int i=1;i<=n;i++){
if(!vis[i])cout<<i<<endl;
}
cout<<f<<endl;
}
例题 #2 [HNOI2015] 菜肴制作¶
知名美食家小 A 被邀请至 ATM 大酒店，为其品评菜肴。ATM 酒店为小 A 准备了 \(n\) 道菜肴，酒店按照为菜肴预估的质量从高到低给予 \(1\) 到 \(n\) 的顺序编号，预估质量最高的菜肴编号为 \(1\)。
由于菜肴之间口味搭配的问题，某些菜肴必须在另一些菜肴之前制作，具体的，一共有 \(m\) 条形如 \(i\) 号菜肴必须先于 \(j\) 号菜肴制作的限制，我们将这样的限制简写为 \((i,j)\)。
现在，酒店希望能求出一个最优的菜肴的制作顺序，使得小 A 能尽量先吃到质量高的菜肴：
也就是说，
-
在满足所有限制的前提下，\(1\) 号菜肴尽量优先制作。
-
在满足所有限制，\(1\) 号菜肴尽量优先制作的前提下，\(2\) 号菜肴尽量优先制作。
-
在满足所有限制，\(1\) 号和 \(2\) 号菜肴尽量优先的前提下，\(3\) 号菜肴尽量优先制作。
-
在满足所有限制，\(1\) 号和 \(2\) 号和 \(3\) 号菜肴尽量优先的前提下，\(4\) 号菜肴尽量优先制作。
-
以此类推。
例 1：共 \(4\) 道菜肴，两条限制 \((3,1)\)、\((4,1)\)，那么制作顺序是 \(3,4,1,2\)。
例 2：共 \(5\) 道菜肴，两条限制 \((5,2)\)、\((4,3)\)，那么制作顺序是 \(1,5,2,4,3\)。
例 1 里，首先考虑 \(1\)，因为有限制 \((3,1)\) 和 \((4,1)\)，所以只有制作完 \(3\) 和 \(4\) 后才能制作 \(1\)，而根据 3，\(3\) 号又应尽量比 \(4\) 号优先，所以当前可确定前三道菜的制作顺序是 \(3,4,1\)；接下来考虑 \(2\)，确定最终的制作顺序是 \(3,4,1,2\)。
例 \(2\) 里，首先制作 \(1\) 是不违背限制的；接下来考虑 \(2\) 时有 \((5,2)\) 的限制，所以接下来先制作 \(5\) 再制作 \(2\)；接下来考虑 \(3\) 时有 \((4,3)\) 的限制，所以接下来先制作 \(4\) 再制作 \(3\)，从而最终的顺序是 \(1,5,2,4,3\)。现在你需要求出这个最优的菜肴制作顺序。无解输出 Impossible!（首字母大写，其余字母小写）
输入格式
第一行是一个正整数 \(t\)，表示数据组数。接下来是 \(t\) 组数据。对于每组数据：第一行两个用空格分开的正整数 \(n\) 和 \(m\)，分别表示菜肴数目和制作顺序限制的条目数。接下来 \(m\) 行，每行两个正整数 \(x,y\)，表示 \(x\) 号菜肴必须先于 \(y\) 号菜肴制作的限制。
输出格式
输出文件仅包含 \(t\) 行，每行 \(n\) 个整数，表示最优的菜肴制作顺序，或者 Impossible! 表示无解。
无解的情况当且仅当存在环。
我们发现再满足全部访问前驱后要求访问的点的编号尽可能小。首先我们考虑求出字典序最小的拓扑排序。
但是交上去发现WA了，可以举出反例：
3→2 4→1，out:3 2 4 1 ans:4 1 3 2。
我们发现至关重要的不是先访问的那个点，而是后访问的那个点。因此我们可以建反图，求出字典序最大的拓扑序，就满足要求了。
// Problem: P3243 [HNOI2015] 菜肴制作
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3243
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Challenger: Erica N
// ----
//
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ull unsigned long long
#define int long long
#define pb push_back
#define itn int
#define ps second
#define pf first
#define rd read()
int read()
{
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() {
cerr << endl;
}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
for (auto v: a) cerr << v << ' ';
err(x...);
}
template<typename T, typename... A>
void err(T a, A... x) {
cerr << a << ' ';
err(x...);
}
#else
#define dbg(...)
#endif
const int N=2e5+5;
const ull P=137;
const int INF=1e18+7;
/*
策略
*/
vector<int> e[N];
int top;
int ind[N];
int ans[N];
priority_queue<int> q;
void add(int a,int b){
e[a].push_back(b);
ind[b]++;
}
bitset<N> vis;
void solve(){
int n=rd,m=rd;
for(int i=1;i<=n;i++){
vis[i]=ind[i]=0;
while(e[i].size())e[i].pop_back();
}
for(int i=1;i<=m;i++){
add(rd,rd);
}
for(int i=1;i<=n;i++){
if(!ind[i])q.push(i);
}
// cdbg("O");
while(q.size()){
int x=q.top();
vis[x]=1;
q.pop();
ans[++top]=x;
for(auto v:e[x]){
ind[v]--;
if(!ind[v])q.push(v);
}
}
for(int i=1;i<=n;i++){
if(!vis[i]&&ind[i]){
puts("Impossible!");
return ;
}
}
while(top){
cout<<ans[top--]<<' ';
}
for(int i=1;i<=n;i++){
if(!vis[i])cout<<i<<' ';
}
cout<<endl;
}
signed main(){
int t=rd;
while(t--){
solve();
}
}
练习 #1 [USACO08JAN] Cow Contest S¶
题目描述
\(N (1 ≤ N ≤ 100)\) cows, conveniently numbered \(1 ~ N\) , are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors.
The contest is conducted in several head-to-head rounds, each between two cows. If cow \(A\) has a greater skill level than cow \(B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B)\), then cow \(A\) will always beat cow \(B\) .
Farmer John is trying to rank the cows by skill level. Given a list the results of \(M (1 ≤ M ≤ 4,500)\) two-cow rounds, determine the number of cows whose ranks can be precisely determined from the results. It is guaranteed that the results of the rounds will not be contradictory.
FJ的 \(N\)（\(1 \leq N \leq 100\)）头奶牛们最近参加了场程序设计竞赛。在赛场上，奶牛们按 \(1, 2, \cdots, N\) 依次编号。每头奶牛的编程能力不尽相同，并且没有哪两头奶牛的水平不相上下，也就是说，奶牛们的编程能力有明确的排名。 整个比赛被分成了若干轮，每一轮是两头指定编号的奶牛的对决。如果编号为 \(A\) 的奶牛的编程能力强于编号为 \(B\) 的奶牛 （\(1 \leq A, B \leq N\)，\(A \neq B\))，那么她们的对决中，编号为 \(A\) 的奶牛总是能胜出。 FJ 想知道奶牛们编程能力的具体排名，于是他找来了奶牛们所有 \(M\)（\(1 \leq M \leq 4,500\)）轮比赛的结果，希望你能根据这些信息，推断出尽可能多的奶牛的编程能力排名。比赛结果保证不会自相矛盾。
输入格式
第一行两个用空格隔开的整数 \(N, M\)。
第 \(2\sim M + 1\) 行，每行为两个用空格隔开的整数 \(A, B\) ，描述了参加某一轮比赛的奶牛的编号，以及结果（每行的第一个数的奶牛为**胜者**）。
输出格式
输出一行一个整数，表示排名可以确定的奶牛的数目。
本题中，因为确定了有解，故是一个DAG。我们考虑什么情况下的排名不能确定
- 有奶牛与他不连通（有向图意义上）
因此我们只需要跑一次连通性判断是否所有点都和i联通就可以判断i了。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define itn int
#define pb push_back
#define rd read()
inline int read() {
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
void write(int out) {
if (out < 0)
putchar('-'), out = -out;
if (out > 9)
write(out / 10);
putchar(out % 10 + '0');
}
#define cdbg(x) cerr<<#x<<" : "<<x<<endl;
const int INF=1e9;
const int N=2e3+5;
/*
策略：
*/
bool d[N][N];
signed main(){
int n=rd,m=rd;
for(int i=1;i<=m;i++){
int a=rd,b=rd;
d[a][b]=1;
}
for(int i=1;i<=n;i++)d[i][i]=1;
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
d[i][j]|=d[i][k]&d[k][j];
}
}
}
int ans=0;
for(int i=1;i<=n;i++){
int cnt=0;
for(int j=1;j<=n;j++){
cnt+=d[i][j]|d[j][i];
}
ans+=cnt==n;
}
cout<<ans<<endl;
return 0;
}
上面是比较偷懒的办法，如果使用拓扑排序的话，我们将每个点作为拓扑排序的起点，进行n次拓扑排序。
得到n种拓扑序列后，比较每个点在每次拓扑排序中的位置,如果该点满足在n种拓扑序列中位置不变,则满足要求。
因为如果有不确定的，那么总有一次拓扑序会使得他的排名发生改变。
拓扑排序一个应用就是给定相邻两个人/数字的大小关系，求最后的排名，或者确定那些元素的排名不确定。
例题 #3 [Wind Festival] Running In The Sky¶
一天的活动过后，所有学生都停下来欣赏夜空下点亮的风筝。\(Curtis\) \(Nishikino\)想要以更近的视角感受一下，所以她跑到空中的风筝上去了(这对于一个妹子来说有点匪夷所思)! 每只风筝上的灯光都有一个亮度 \(k_i\). 由于风的作用，一些风筝缠在了一起。但是这并不会破坏美妙的气氛，缠在一起的风筝会将灯光汇聚起来，形成更亮的光源！
\(Curtis\) \(Nishikino\)已经知道了一些风筝间的关系，比如给出一对风筝\((a,b)\), 这意味着她可以从 \(a\) 跑到 \(b\) 上去，但是不能返回。
现在，请帮她找到一条路径(她可以到达一只风筝多次，但只在第一次到达时她会去感受上面的灯光), 使得她可以感受到最多的光亮。同时请告诉她这条路径上单只风筝的最大亮度，如果有多条符合条件的路径，输出能产生最大单只风筝亮度的答案。
输入格式
第一行两个整数 \(n\) 和 \(m\). \(n\) 是风筝的数量, \(m\) 是风筝间关系对的数量.
接下来一行 \(n\) 个整数 \(k_i\).
接下来 \(m\) 行, 每行两个整数 \(a\) 和 \(b\), 即\(Curtis\)可以从 \(a\) 跑到 \(b\).
输出格式
一行两个整数。\(Curtis\)在计算出的路径上感受到的亮度和，这条路径上的单只风筝最大亮度.
对于 \(100\%\) 的数据, \(0<n\le2\times10^5,\ 0<m\le5\times10^5,\ 0<k\le200\).
缩点后再拓扑排序dp
// Problem: P4742 [Wind Festival] Running In The Sky
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4742
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Challenger: Erica N
// ----
//
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ull unsigned long long
#define int long long
#define pb push_back
#define itn int
#define ps second
#define pf first
#define rd read()
int read()
{
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() {
cerr << endl;
}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
for (auto v: a) cerr << v << ' ';
err(x...);
}
template<typename T, typename... A>
void err(T a, A... x) {
cerr << a << ' ';
err(x...);
}
#else
#define dbg(...)
#endif
const int N=2e5+5;
const ull P=137;
const int INF=1e18+7;
/*
策略
*/
int stk[N],top;
int low[N],dfn[N];
int tim;
int f[N],h[N];
int ind[N];
int mx[N],sum[N];
int cnt;
int scc[N];
int a[N];
bitset<N> vis;
queue<int> q;
vector<int> e[N],g[N];
map<int,map<int,int> > conn;
void add(int b,int a){
e[a].pb(b);
}
void addg(int a,int b){
if(conn[a][b])return ;
conn[a][b]=1;
// cdbg(a,b);
g[a].pb(b);
ind[b]++;
}
void tarjan(int x){
dfn[x]=low[x]=++tim;
vis[x]=1;
stk[++top]=x;
for(auto v:e[x]){
if(!dfn[v]){
tarjan(v);
low[x]=min(low[x],low[v]);
}else if(vis[v])low[x]=min(low[x],dfn[v]); //!!
}
if(low[x]==dfn[x]){
int y;
++cnt;
do{
y=stk[top--];
scc[y]=cnt;
vis[y]=0;//!!
mx[cnt]=max(mx[cnt],a[y]);
sum[cnt]+=a[y];
}while(y!=x);
}
}
signed main(){
int n=rd,m=rd;
for(int i=1;i<=n;i++){
a[i]=rd;
}
for(int i=1;i<=m;i++){
add(rd,rd);
}
for(int i=1;i<=n;i++){
if(!dfn[i])
tarjan(i);
}
for(int i=1;i<=n;i++){
for(auto v:e[i]){
if(scc[i]!=scc[v])addg(scc[i],scc[v]);
}
}
// cdbg("oK");
// for(int i=1;i<=n;i++)cdbg(scc[i]);
for(int i=1;i<=cnt;i++)f[i]=sum[i],h[i]=mx[i];
for(int i=1;i<=cnt;i++){
// cdbg(sum[i]);
if(ind[i]==0)q.push(i);
}
while(q.size()){
int x=q.front();
q.pop();
for(auto v:g[x]){
if(f[v]<f[x]+sum[v]){
// cdbg(v);
f[v]=f[x]+sum[v];
h[v]=max(h[x],mx[v]);
}else if(f[v]==f[x]+sum[v]){
// cdbg(v);
h[v]=max(h[v],max(h[x],mx[v]));
}
ind[v]--;
if(!ind[v])q.push(v);
}
}
// cdbg(f[3]);
int sum=0,mx=0;
for(int i=1;i<=cnt;i++){
if(f[i]>sum||(f[i]==sum&&h[i]>mx)){
sum=f[i];
mx=h[i];
}
}
cout<<sum<<' '<<mx<<endl;
}