51 lines
1.4 KiB
C++
51 lines
1.4 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int N = 5005; //种类上限
|
||
const int M = 500005; //关系数上限
|
||
int n; //种类
|
||
int m; //关系数
|
||
vector<int> edge[N]; //保存DAG图的邻接表
|
||
queue<int> q; //广搜的队列
|
||
int ind[N]; //入度
|
||
|
||
/**
|
||
* 测试用例：
|
||
3 3
|
||
1 2
|
||
2 3
|
||
1 3
|
||
|
||
输出拓扑排序,注意拓扑排序不是唯一的
|
||
1 2 3
|
||
* @return
|
||
*/
|
||
|
||
int main() {
|
||
cin >> n >> m;
|
||
//m种关系
|
||
for (int i = 1; i <= m; i++) {
|
||
int x, y;
|
||
cin >> x >> y;
|
||
ind[y]++; //点y的入度+1
|
||
edge[x].push_back(y); //用邻接表记录下
|
||
}
|
||
//找到所有入度为0的点，放入广度优先搜索的队列
|
||
for (int i = 1; i <= n; i++) if (!ind[i]) q.push(i);
|
||
|
||
//广度优先搜索DAG，就是拓扑排序的模板
|
||
while (!q.empty()) {
|
||
int x = q.front();
|
||
q.pop();
|
||
//输出拓扑序
|
||
cout << x << " ";
|
||
for (int i = 0; i < edge[x].size(); i++) { //遍历所有出边
|
||
int y = edge[x][i]; //目标结点
|
||
//对接点入度-1，抹去这条入边
|
||
ind[y]--;
|
||
//如果入度为0，则入队列，准备处理它
|
||
if (!ind[y]) q.push(y);
|
||
}
|
||
}
|
||
return 0;
|
||
} |