拓扑排序详解

定义

什么是拓扑排序？

拓扑排序就可以理解为如果要访问i点，之前必须访问j点，给出一个合法的访问顺序，联系到生活中就可以理解为你要泡茶，但你之前必须烧水。那么烧水-泡茶就是一种合理的拓扑排序。 （够形象了吧

实现

探寻规律的话，发现tp（自创简称懒得打字）里的第一件事一定是不需要之前做什么事情的，此时做完了之后你应该做下面一件事，做完的事情不考虑，接下来同上，就能发现规律。

联系到图上，怎么tp？ （假设有向图上i点能到j点为i需要在j点之前完成）

每次寻找一个入度为0的点，将其输出，然后把能到达的节点入度减一，如果还有入度为0的继续。

（不要以为这样就结束了 ， 想想一个图的tp一定存在吗？）

当然，图中出现环的时候此时一定没有tp ， 如何判断？ （这个方法很多，最简单的就是判断拓扑序列长度小于节点个数就没有拓扑排序

例子

从1出发，砍掉入度，发现2为0，继续，发现4为0，继续最后是3. PS：//一开始就要把所有入度为0的全部入队，如果有多个连通块呢？

话不多说上代码

#include <bits/stdc++.h>
using namespace std;
int indgree[1000];
vector<int> g[1000];
int n, m;
vector<int> seq;
// 邻接表大法好
// seq 存储拓扑
void top() {
  queue<int> q;
  for (int i = 0; i <= n - 1; ++i) {
    if (indgree[i] == 0) {
      q.push(i);
    }
  }
  while (!q.empty()) {
    int cur = q.front();
    seq.push_back(cur);
    q.pop();
    for (int i = 0; i < g[cur].size(); ++i) {
      --indgree[g[cur][i]];
      if (indgree[g[cur][i]] == 0) {
        q.push(g[cur][i]);
      }
    }
  }
  if (seq.size() != n) {
    cout << "NO" << endl;
  } else {
    cout << "YES" << endl;
  }
}
int main() {
  freopen("legal.in", "r", stdin);
  freopen("legal.out", "w", stdout);
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    g[x].push_back(y);
    ++indgree[y];
  }
  top();
}

（觉得不烂的给个三连吧 （走错片场了抱歉，给个好评吧

拓扑排序详解 （？

原文：https://www.cnblogs.com/Sikonihigh/p/14407842.html