TopoSort(拓撲排序)
其實說白了,拓撲排序就是一個廣度優先搜索。
拓撲排序的方法如下:
(1)從有向圖中選擇一個沒有前驅(即入度為0)的頂點并且輸出它.
(2)從網中刪去該頂點,并且刪去從該頂點發出的全部有向邊.
(3)重復上述兩步,直到剩余的網中不再存在沒有前趨的頂點為止.
本題目是采用的鄰接表存儲方法。
具體的實現是用vector數組。
題目:HDU 1285 http://acm.hdu.edu.cn/showproblem.php?pid=1285
View Code
#include "iostream" #include "vector" #include "queue" using namespace std; #define MAX 505 int InDeg[MAX]; int n, m, Count; int Ans[MAX]; void TopoSort(vector<int> v[]) { priority_queue<int, vector<int>, greater<int> > PQ; for(int i=1; i<=n; i++) //找出入度為0的點并放入優先隊列 if(InDeg[i]==0) PQ.push(i); while(!PQ.empty()) //BFS { int Tmp = PQ.top(); PQ.pop(); Ans[Count++] = Tmp; for(int i=0; i<v[Tmp].size(); i++) { InDeg[v[Tmp][i]]--; if(InDeg[v[Tmp][i]]==0) PQ.push(v[Tmp][i]); } } } int main() { int x, y; while(cin>>n>>m) { vector<int> V[MAX]; memset(Ans, 0, sizeof(Ans)); Count = 0; memset(InDeg, 0, sizeof(InDeg)); for(int i=0; i<m; i++) { cin>>x>>y; InDeg[y]++; V[x].push_back(y); } TopoSort(V); for(int i=0; i<Count-1; i++) cout<<Ans[i]<<" "; cout<<Ans[Count-1]<<endl; } }
posted on 2012-04-11 18:36 More study needed. 閱讀(957) 評論(0) 收藏 舉報

浙公網安備 33010602011771號