拓補排序

概要

在一個有向無環圖中，對其所有頂點進行拓補排序，就是将所有頂點排成一個序列，并使得序列中所有的點滿足對于邊<u,v>,若u到v是可達的，則u在拓補序列中一定出現在v之前。

過程

①找到目前入度為0的點，加入拓補序列

②将找到的入度為0的點的出邊和該點删除

③重複上面兩個步驟

簡要實作

最後

代碼

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 80112002;
int g[5010][5010];
queue<int>q;
int in_degree[5010];
int f[5010];
int main()
{
  int n,m;
  cin>>n>>m;
  while(m--)
  {
    int u,v;
    cin>>u>>v;
    g[u][v] = 1;
    in_degree[v]++;
  }
  for(int i = 1; i <= n; i++)
  {
    if(in_degree[i] == 0)
    {
      f[i] = 1;
      q.push(i);
    }
  }
  ll ans = 0;
  while(!q.empty())
  {
    int k = q.front();
    q.pop();
    cout<<k<<" ";
    for(int i = 1; i <= n; i++)
    {
      if(!g[k][i])continue;
      in_degree[i]--;
      if(!in_degree[i])
      {
        q.push(i);
      }
    }
  }
}