拓扑排序
大约 3 分钟约 965 字
拓扑排序
给定一个有向无环图(DAG),排出所有顶点的一个序列A满足:对于图中每条有向边(x,y),x在A中都出现在y之前,则A是该图中的顶点的一个拓扑序
拓扑排序可以判断 有向图中是否有环 ,可以生成拓扑序列
Kahn(卡恩)算法
- e[x]存点x的邻点,res存拓扑序列,d[x]存x的入度
算法流程:核心用队列维护一个入度为0的节点的集合。
- 初始化,队列q压入所有入度为0的点;
- 每次从q中取出一个点x放入数组res;
- 然后将×的所有出边删除。若将边(x,y)删除后,y的入度变为0,则将y压入q中
- 不断重复2,3过程,直到队列q为空。
- res中的元素个数等于n,则有拓扑序;否则,有环。
题目-有向图的拓扑序列
链接:https://www.acwing.com/problem/content/850/
给定一个 个点 条边的有向图,点的编号是 到 ,图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出 。
若一个由图中所有点构成的序列 满足:对于图中的每条边 , 在 中都出现在 之前,则称 是该图的一个拓扑序列。
输入格式
第一行包含两个整数 和 。
接下来 行,每行包含两个整数 和 ,表示存在一条从点 到点 的有向边 。
输出格式
共一行,如果存在拓扑序列,则输出任意一个合法的拓扑序列即可。
否则输出 。
数据范围
输入样例:
3 3
1 2
2 3
1 3
输出样例:
1 2 3
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int n, m;
vector<int> e[N], res;
vector<int> d(N);
bool topsort() {
queue<int> q;
for (int i = 1; i <= n; i++) {
if (d[i] == 0) q.push(i);
}
while (q.size()) {
auto t = q.front();
q.pop();
res.push_back(t);
for (auto y: e[t]) {
if (--d[y] == 0) q.push(y);
}
}
return res.size() == n;
}
signed main() {
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
e[x].push_back(y);
d[y]++;
}
if (topsort()) {
for (const auto &item: res) {
cout << item << " ";
}
} else {
cout << -1 << endl;
}
return 0;
}
DFS算法
- e[x]存点x的邻点,res存拓扑序列,d[x]存x的入度
算法的核心是变色法,一路搜一路给点变色,如果有拓扑序,每个点的颜色都会从0→-1→1,经历三次变色。
- 初始状态,所有点染色为0。
- 枚举每个点,进入×点,把x染色为-1。然后,枚举x的儿子y,如果y的颜色为0,说明没碰过该点,进入y继续走,
- 如果枚举完×的儿子,没发现环,则×染色为1,并把×压入tp数组
- 如果发现有个熊孩子的颜色为-1,说明回到了祖先节点,发现了环,则一路返回false,退出程序
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
vector<int> e[N], res, c(N);
int n, m;
int dfs(int x) {
c[x] = -1;
for (auto y: e[x]) {
if (c[y] == -1) return 0;//有环
else if (c[y] == 0) {
int t = dfs(y);
if (t == 0) return 0;
}
}
c[x] = 1;
res.push_back(x);
return 1;
}
bool topsort() {
for (int i = 1; i <= n; i++) {
if (c[i] == 0) {
int t = dfs(i);
if (t == 0) return 0;
}
}
std::reverse(res.begin(), res.end());
return 1;
}
signed main() {
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
e[x].push_back(y);
}
if (topsort()) {
for (const auto &item: res) {
cout << item << " ";
}
} else {
cout << -1 << endl;
}
return 0;
}