acwing算法提高之图论--拓扑排序

news/2024/5/9 7:31:23

1 介绍

本专题用来记录拓扑排序相关的题目。

求拓扑序列算法的关键步骤：

把入度为0的结点插入队列q。
弹出队头t（将t记录下来），遍历队头t的下一个结点，将其入度减1。操作之后，如果其值为0，则插入队列q。
重复进行步骤2，直至队列q为空。
弹出的元素组成的序列就是一个拓扑序列。

有向无环图等价于图中存在拓扑序列！

2 训练

题目1：1191家谱树

C++代码如下，

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>using namespace std;const int N = 110;
int n;
int din[N];
vector<vector<int>> g(N);int main() {cin >> n;for (int i = 1; i <= n; ++i) {int t;while (cin >> t, t) {g[i].emplace_back(t);din[t]++;}}queue<int> q;for (int i = 1; i <= n; ++i) {if (din[i] == 0) {q.push(i);}}vector<int> res;while (!q.empty()) { //队列中存储的是，目前所有入度为0的结点int a = q.front();q.pop();res.emplace_back(a);for (auto b : g[a]) {din[b]--;if (din[b] == 0) {q.push(b);}}}for (auto x : res) cout << x << " ";cout << endl;return 0;
}

题目2：1192奖金

C++代码如下，

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>using namespace std;const int N = 10010;
int n, m;
vector<vector<int>> g(N);
int dist[N];
int din[N];int main() {cin >> n >> m;for (int i = 0; i < m; ++i) {int a, b;cin >> a >> b;g[b].emplace_back(a);din[a]++;}memset(dist, 0x3f, sizeof dist);queue<int> q;for (int i = 1; i <= n; ++i) {if (din[i] == 0) {q.push(i);dist[i] = 100;}}int cnt = 0;//入度为0的结点总数while (!q.empty()) {int a = q.front();q.pop();cnt++;for (int b : g[a]) {din[b]--;if (din[b] == 0) {q.push(b);dist[b] = dist[a] + 1;}}}if (cnt != n) puts("Poor Xed");else {int sum = 0;for (int i = 1; i <= n; ++i) sum += dist[i];cout << sum << endl;}return 0;
}

题目3：164可达性统计

C++代码如下，

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <bitset>
#include <vector>using namespace std;const int N = 30010;
int n, m;
int din[N];
bitset<N> f[N]; //f[i]表示结点i能走到的结点
vector<vector<int>> g(N);
vector<int> res;void toposort() {queue<int> q;for (int i = 1; i <= n; ++i) {if (din[i] == 0) {q.push(i);}}while (!q.empty()) {int a = q.front();q.pop();res.emplace_back(a);for (auto b : g[a]) {din[b]--;if (din[b] == 0) {q.push(b);}}}return;
}int main() {cin >> n >> m;for (int i = 0; i < m; ++i) {int a, b;cin >> a >> b;din[b]++;g[a].emplace_back(b);}toposort();for (int i = res.size() - 1; i >= 0; --i) {int a = res[i];f[a][a] = 1;for (auto b : g[a]) {f[a] |= f[b];}}for (int i = 1; i <= n; ++i) {cout << f[i].count() << endl;}return 0;
}

题目4：456车站分级

C++代码如下，

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 2010, M = 1000010;int n, m;
int h[N], e[M], ne[M], w[M], idx;
int q[N], d[N];
int dist[N];
bool st[N];void add(int a, int b, int c) {e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;d[b]++;
}void topsort() {int hh = 0, tt = -1;for (int i = 1; i <= n + m; ++i) {if (!d[i]) {q[++tt] = i;}}while (hh <= tt) {int t = q[hh++];for (int i = h[t]; ~i; i = ne[i]) {int j = e[i];if (--d[j] == 0) {q[++tt] = j;}}}
}int main() {scanf("%d%d", &n, &m);memset(h, -1, sizeof h);for (int i = 1; i <= m; ++i) {memset(st, 0, sizeof st);int cnt;scanf("%d", &cnt);int start = n, end = 1;while (cnt--) {int stop;scanf("%d", &stop);start = min(start, stop);end = max(end, stop);st[stop] = true;}int ver = n + i;for (int j = start; j <= end; ++j) {if (!st[j]) add(j, ver, 0);else add(ver, j, 1);}}topsort();for (int i = 1; i <= n; ++i) dist[i] = 1;for (int i = 0; i < n + m; ++i) {int j = q[i];for (int k = h[j]; ~k; k = ne[k]) {dist[e[k]] = max(dist[e[k]], dist[j] + w[k]);}}int res = 0;for (int i = 1; i <= n; ++i) res = max(res, dist[i]);printf("%d\n", res);return 0;
}