Topological-sorting

Topological-sorting

Charles Lv7
  2023-01-04 22:51:15 2023-01-04 22:51:15 Created   2023-07-30 10:52:49 2023-07-30 10:52:49 Updated      1.6k Words  6 Mins  

Topological-sorting

拓扑排序

定义

拓扑排序是一类用于处理 DAG（Directed acyclic graph），即有向无环图上的问题。
所谓拓扑排序就是将AOV-网中所有顶点排成一个线性序列，该序列满足：若在AOV-网中由顶点vi到顶点 vj有一条路径，则在该线性序列中的顶点 Vi必定在顶点Vj之前。

拓扑排序的实现原理

定义两个辅助数组结构分别用来存放各顶点入度和记录拓扑排序的顶点序号。从第一个无入度的顶点开始，将所有无入度的顶点依次输出并从已有图中摘除，同时将此结点与其他结点所依附的边摘除，最终输出的顶点序列就是拓扑排序序列，此处需要注意的是：有些有向无环图的拓扑排序序列的结果并不唯一(可能有多个结点都无入度)

注：如果最后不存在入度为0的节点，那就说明有环，不存在拓扑排序，也就是很多题目的无解的情况。

拓扑排序的主要步骤

  1. 初始化队列，将入度为 0 的节点放入队列。
  2. 取出队首，遍历其出边，将能够到达的点入度减一，同时维护答案数组。
  3. 若在此时一个点的入度变为 0，那么将其加入队列。
  4. 回到第二步，直到队列为空。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int ind[N], f[N], a[N];
// ind--入度   f--答案   a--时间
vector<int> edge[N];
queue<int> q;
void topological_sort() {
    // 步骤一
    for (int i = 1; i <= n; i++) {
        if (ind[i] == 0) {
            q.push(i);
            f[i] = a[i];
        }
    };
    while (!q.empty()) {
        int rhs = q.front();
        q.pop();
        // 步骤二
        for (int i = 0; i < edge[rhs].size(); i++) {
            int u = edge[rhs][i];
            ind[u]--;
            if (ind[u] == 0)
                q.push(u);  
            // 步骤三
            f[u] = max(f[u], f[rhs] + a[u]);
        }
    }
}

小技巧：拓扑排序的更好的理解方式实际上是一种特殊的图bfs遍历。

模板题

杂务

题目描述

John的农场在给奶牛挤奶前有很多杂务要完成，每一项杂务都需要一定的时间来完成它。比如：他们要将奶牛集合起来，将他们赶进牛棚，为奶牛清洗乳房以及一些其它工作。尽早将所有杂务完成是必要的，因为这样才有更多时间挤出更多的牛奶。当然，有些杂务必须在另一些杂务完成的情况下才能进行。比如：只有将奶牛赶进牛棚才能开始为它清洗乳房，还有在未给奶牛清洗乳房之前不能挤奶。我们把这些工作称为完成本项工作的准备工作。至少有一项杂务不要求有准备工作，这个可以最早着手完成的工作，标记为杂务$1$。John有需要完成的$n$个杂务的清单，并且这份清单是有一定顺序的，杂务$k(k>1)$的准备工作只可能在杂务$1$至$k-1$中。

写一个程序从$1$到$n$读入每个杂务的工作说明。计算出所有杂务都被完成的最短时间。当然互相没有关系的杂务可以同时工作，并且，你可以假定John的农场有足够多的工人来同时完成任意多项任务。

输入格式

第1行：一个整数$n$，必须完成的杂务的数目($3 \le n \le 10,000$)；

第$2$至$(n+1)$行： 共有$n$行，每行有一些用$1$个空格隔开的整数，分别表示：

* 工作序号($1$至$n$,在输入文件中是有序的)；

* 完成工作所需要的时间$len(1 \le len \le 100)$；

* 一些必须完成的准备工作，总数不超过$100$个，由一个数字$0$结束。有些杂务没有需要准备的工作只描述一个单独的$0$，整个输入文件中不会出现多余的空格。

输出格式

一个整数，表示完成所有杂务所需的最短时间。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
7
1 5 0
2 2 1 0
3 3 2 0
4 6 1 0
5 1 2 4 0
6 8 2 4 0
7 4 3 5 6 0

样例输出 #1

1
23

AC代码

笔者当时并没有注意到这题是拓扑排序，是用dp AC的，在此引用了讨论区的拓扑排序的代码，本人dp写的代码也一并给出。

folding code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
#define M 10007
#define N 1007
#define INF 0x3f3f3f3f
#define ll long long
#define db double
vector<int> g[M];
int len[M], t[M];
int n;
// dp
int dfs(int root) {
    if (t[root])
        return t[root];
    for (int i = 0; i < g[root].size(); i++)
        t[root] = max(t[root], dfs(g[root][i]));
    t[root] += len[root];
    return t[root];
}
int main() {
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin >> n;
    int id, work;
    for (int i = 1; i <= n; i++) {
        cin >> id >> len[i];
        while (1) {
            cin >> work;
            if (!work) {
                break;
            }
            g[work].push_back(id);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, dfs(i));
    cout << ans << endl;
    return 0;
}

folding code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <vector>
#include <queue>

#define ll long long

using namespace std;

inline int read() {
	int x=0,f=1;
	char ch=getchar();
	while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x*f;
}

const int N=500005;

int ind[N],f[N],a[N];  //ind--入度   f--答案   a--时间
vector <int> edge[N];
queue <int> q;

int main() {
	int n=read();
	for (int i=1;i<=n;i++) {
		int x=read();
		a[i]=read();
		while (int y=read()) {
			if (!y) break;
			edge[y].push_back(x);
            ind[x]++;
		}
	}
    //步骤一
	for (int i=1;i<=n;i++) {
		if (ind[i]==0) {
			q.push(i);
			f[i]=a[i];
		}
	};
	while (!q.empty()) {
		int rhs=q.front();
		q.pop();
        //步骤二
		for (int i=0;i<edge[rhs].size();i++) {
			int u=edge[rhs][i];
			ind[u]--;
			if (ind[u]==0) q.push(u);  //步骤三
			f[u]=max(f[u],f[rhs]+a[u]);
		}
	}
	int ans=0;
	for (int i=1;i<=n;i++) {
		ans=max(ans,f[i]);   //统计答案
	}
	printf("%d\n",ans);
	return 0;
}

之后通过讨论区了解到我用的dp实际上是dfs形式的拓扑排序，而正常的拓扑排序为bfs~

  • Title: Topological-sorting
  • Author: Charles
  • Created at : 2023-01-04 22:51:15
  • Updated at : 2023-07-30 10:52:49
  • Link: https://charles2530.github.io/2023/01/04/topological-sorting/
  • License: This work is licensed under CC BY-NC-SA 4.0.
recommend_articles
OS_theory_6 OS_theory_6 Swift-note-24 Swift-note-24 html-note-2 html-note-2
recommend_articles
OS_theory_6 OS_theory_6 Swift-note-24 Swift-note-24
Comments
On this page
Topological-sorting
  1. Topological-sorting
    1. 拓扑排序
      1. 定义
      2. 拓扑排序的实现原理
      3. 拓扑排序的主要步骤
    2. 模板题
      1. 杂务
      2. 题目描述
      3. 输入格式
      4. 输出格式
      5. 样例 #1
        1. 样例输入 #1
        2. 样例输出 #1
    3. AC代码