当前位置：首页 > news >正文

图论·拓扑排序

news 2025/3/13 21:54:44

拓扑排序

有向无环图的遍历
检查有向图是否连通/有环

核心操作

统计度数，对于度为0的点作为起始点，添加度为0的点作为遍历
如何验证有环？注意不建议直接模拟，如果出现环这起始点的度一定不为0，肯定会少遍历一些点！这样遍历得到的点和图中的点数量不一致
使用BFS作为搜索媒介

#include<bits/stdc++.h>
#define MAX_VALUE 10009
using ll = long long;
using namespace std;
int n, m, s, t;
vector<list<int>>graph(100006,list<int>());
vector<int>indegrees(100006, 0);
vector<int>res;
void solve() {cin >> n >> m;while (m--) {cin >> s >> t;graph[s].push_back(t);indegrees[t]++;}queue<int>q;for (int i = 0; i <= n-1; i++) {if (!indegrees[i]) {q.push(i);}}while (!q.empty()) {int cur = q.front();q.pop();res.push_back(cur);for (auto item : graph[cur]) {if (--indegrees[item]==0) {q.push(item);}}}if (res.size() == n) {for (int i = 0; i < n - 1; i++) cout << res[i] << " ";cout << res[n - 1];}else cout << -1 << endl;}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);solve();
}

以下为例题

P4017 最大食物链计数

题目背景

你知道食物链吗？Delia 生物考试的时候，数食物链条数的题目全都错了，因为她总是重复数了几条或漏掉了几条。于是她来就来求助你，然而你也不会啊！写一个程序来帮帮她吧。

题目描述

给你一个食物网，你要求出这个食物网中最大食物链的数量。

（这里的“最大食物链”，指的是生物学意义上的食物链，即最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者。）

Delia 非常急，所以你只有 $1$ 秒的时间。

由于这个结果可能过大，你只需要输出总数模上 $80112002$ 的结果。

输入格式

第一行，两个正整数 $n 、 m$ ，表示生物种类 $n$ 和吃与被吃的关系数 $m$ 。

接下来 $m$ 行，每行两个正整数，表示被吃的生物A和吃A的生物B。

输出格式

一行一个整数，为最大食物链数量模上 $80112002$ 的结果。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

各测试点满足以下约定：

【补充说明】

数据中不会出现环

题解1：拓扑排序

时间复杂度： $O (n + e)$
DFS理论上也可以使用，但是只能过前两个用例。

#include<bits/stdc++.h>
#define MAX_VALUE 10000009
#define mod 80112002
using ll = long long;
using namespace std;
int n, m,a,b,ans=0;
vector<int>indegrees(5009, 0);
vector<list<int>>graph(5009, list<int>());
vector<int>producers;
vector<int>res(5009, 0);
void solve() {cin >> n >> m;while (m--) {cin >> a >> b;graph[a].push_back(b);indegrees[b]++;}for (int i = 1; i <= n; i++) {if (!indegrees[i]) {producers.push_back(i);res[i] = 1;//1条食物链}}queue<int>q;for (auto producer : producers) {q.push(producer);}while (!q.empty()) {int cur = q.front();q.pop();//cout << "cur:" << cur << endl;if (!graph[cur].size()) {ans = (ans + res[cur]) % mod;}for (auto item : graph[cur]) {if (!--indegrees[item]) {q.push(item);}res[item] = (res[item] + res[cur])% mod;//cout << "item:" << item << " res[item]:" << res[item] << endl;}//for (int i = 1; i <= n; i++) {//	cout << res[i] << " ";//}//cout << endl;}cout << ans;
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);solve();
}

题解2：DFS

对入度为0的进行DFS，探索所有路径，就是所有生物链

#include<bits/stdc++.h>
#define MAX_VALUE 10000009
#define mod 80112002
using ll = long long;
using namespace std;
int n, m,a,b,ans=0;
vector<int>indegrees(5009, 0);
vector<list<int>>graph(5009, list<int>());
vector<int>producers;
int visited[5009];
void dfs(int start,int * visited) {//cout << "current node:" << start << endl;if (!graph[start].size()) {ans=(ans+1)% mod;//cout << endl;return;}for (auto item : graph[start]) {if (!visited[item]) {visited[item] = 1;dfs(item,visited);visited[item] = 0;}}
}
void solve() {cin >> n >> m;while (m--) {cin >> a >> b;graph[a].push_back(b);indegrees[b]++;}for (int i = 1; i <= n; i++) {if (!indegrees[i]) {producers.push_back(i);}}for (auto producer : producers) {if (!graph[producer].size()) {// no consumercontinue;}memset(visited, 0, sizeof(visited));visited[producer] = 1;dfs(producer, visited);}cout << ans;
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);solve();
}