Topo排序算法：1.有向图判环 2.找做事先后顺序（前置课程）3.分层（什么事可以同时做）
复习相关知识：
拓扑排序算法：kahn(卡恩)算法基于BFS和基于DFS的算法(只有有向无环图才能产生拓扑序列）
卡恩算法：时间复杂度O(v+e)（无环）
卡恩算法模板：
#include<iostream>
#include<queue>
using namespace std;
#define maxn 5005
int n, m;//点编号从1到n
struct edge {
int v, next;
}e[maxn];
int cnt;//边数组下标
int head[maxn];
int ind[maxn];//顶点的入度数组
int topo[maxn], k;//存拓扑序列，下标为k
void add(int x, int y) {
cnt++;
e[cnt].v = y;
e[cnt].next = head[x];
head[x] = cnt;
cnt++;
}
bool kahn() {
int u, v;
queue<int>q;
for (int i = 1; i <= n; i++) {
if (ind[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
u = q.front();
q.pop();
k++, topo[k] = u;
for (int i = head[u]; i != -1; i = e[i].next) {
v = e[i].v;
ind[v]--;//入度减1
if (ind[v] == 0) {
q.push(v);
}
}
}
if (k == n) {
return 1;
}
else {//有环,找不到入度为0的点
return 0;
}
}
int main() {
int x, y;
memset(head, -1, sizeof(head));
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d %d", &x, &y);
add(x, y);
ind[y]++;//入度加1
}
if (kahn() == 1) {
for (int i = 1; i <= k; i++) {
printf("%d ", topo[i]);
}
}
else {
printf("含环\n");
}
return 0;
}
//5 5
//1 2
//2 4
//3 2
//3 4
//4 5
2,基于DFS的算法模板：倒着找，倒着输出（用栈）
通过在搜索过程中加三种状态0 1 2来判环
#include<iostream>
#include<queue>
#include<stack>
using namespace std;
#define maxn 5005
int n, m;//点编号从1到n
stack<int>s;
struct edge {
int v, next;
}e[maxn];
int cnt;//边数组下标
int head[maxn];
int ind[maxn];//顶点的入度数组
int topo[maxn], k;//存拓扑序列，下标为k
int vis[maxn];//状态数组0 1 2
int flag = 0;//标记是否有环
void add(int x, int y) {
cnt++;
e[cnt].v = y;
e[cnt].next = head[x];
head[x] = cnt;
cnt++;
}
void dfs(int u) {
vis[u] = 1;//处于搜索中
int v;
for (int i = head[u]; i != -1; i = e[i].next) {
v = e[i].v;
if (vis[v] == 1) {//搜索中
flag = 1;//有环
return;
}
else if (vis[v] == 0) {//没有被搜索过
dfs(v);
if (flag == 1) {//有环
return;
}
}
}
//没有返回说明u后面全部dfs结束且没出现环，应该把u往回退了
vis[u] = 2;
s.push(u);
}
int main() {
int x, y;
memset(head, -1, sizeof(head));
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d %d", &x, &y);
add(x, y);
}
for (int i = 1; i <= n; i++) {
if (vis[i] == 0) {
dfs(i);
}
}
if (flag == 0) {
while (!s.empty()) {
printf("%d ", s.top());
s.pop();
}
}
else {
printf("含有环");
}
return 0;
}
//5 5
//1 2
//2 4
//3 2
//3 4
//4 5