拓撲排序

在一個有向無環圖中，對所有的節點進行排序，要求沒有一個節點指向它前面的節點。

思想：

先統計所有節點的入度，對于入度為0的節點就可以分離出來，然后把這個節點指向的節點的入度減一。

一直做改操作，直到所有的節點都被分離出來。

如果最后不存在入度為0的節點，那就說明有環，不存在拓撲排序，也就是很多題目的無解的情況。

1->3->4->6->2->5(不唯一)

?

?

C++代碼：

#include <bits/stdc++.h> #define N 105 using namespace std;int main() {vector <int> m[N];queue <int> q;//有些拓撲排序要求字典序最小什么的，那就把隊列換成優先隊列就好了。//priority_queue<int,vector<int>,greater<int> >q;vector <int> ans;int in[N];memset(in,0,sizeof(in));int v,e;cin>>v>>e;for(int i=0;i<e;i++){int a,b;cin>>a>>b;m[a].push_back(b);}for(int i=1;i<=v;i++){for(int j=0;j<m[i].size();j++){in[m[i][j]]++;}}for(int i=1;i<=v;i++)if(in[i]==0) q.push(i);while(!q.empty()){int p=q.front();q.pop();ans.push_back(p);for(int i=0;i<m[p].size();i++){int y=m[p][i];in[y]--;if(in[y]==0)q.push(y);}}if(ans.size()==v){for(int i=0;i<ans.size();i++)printf( "%d ",ans[i] );printf("\n");}else printf("No Answer!\n"); }

?

轉載于:https://www.cnblogs.com/LMIx/p/10730614.html

總結

以上是生活随笔為你收集整理的拓扑排序+代码的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。