? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 拓?fù)渑判?/p>

一.定義

??? 對一個有向無環(huán)圖(Directed Acyclic Graph簡稱DAG)G進(jìn)行拓?fù)渑判?#xff0c;是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若<u，v> ∈E(G)，則u在線性序列中出現(xiàn)在v之前。

?? 通常，這樣的線性序列稱為滿足拓?fù)浯涡?Topological Order)的序列，簡稱拓?fù)湫蛄小?/p>

?? 注意:

?? 1)只有有向無環(huán)圖才存在拓?fù)湫蛄?

?? 2)對于一個DAG,可能存在多個拓?fù)湫蛄?#xff08;此題已經(jīng)規(guī)定了數(shù)字的優(yōu)先級，所以答案唯一）;

?

二.拓?fù)湫蛄兴惴ㄋ枷?/p>

?(1)從有向圖中選取一個沒有前驅(qū)(即入度為0)的頂點，并輸出之;

?(2)從有向圖中刪去此頂點以及所有以它為尾的弧;

重復(fù)上述兩步，直至圖空，或者圖不空但找不到無前驅(qū)的頂點為止。 #include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <queue> #include<functional> #define MAXSIZE 100005 using namespace std;vector<int>G[MAXSIZE]; priority_queue<int ,vector<int>, less<int> > q; int in[MAXSIZE];int main() {int T,n,m,a,b;scanf("%d",&T);while(T--){memset(in,0,sizeof(in));vector<int> ans;for(int i=0;i<MAXSIZE;i++)G[i].clear();scanf("%d%d",&n,&m);while(m--){scanf("%d%d",&a,&b);in[a]++;G[b].push_back(a);}for(int i=1;i<=n;i++)if(!in[i]) q.push(i);while(!q.empty()){int u=q.top();ans.push_back(u);q.pop();int len=G[u].size();for(int i=0;i<len;i++){int v=G[u][i];in[v]--;if(!in[v])q.push(v);}}int len=ans.size();for(int i=len-1;i>=0;i--)printf("%d%c",ans[i],i==0?'\n':' ');}return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/alan-W/p/6640008.html

總結(jié)

以上是生活随笔為你收集整理的HDU 4857 逃生（拓扑排序）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。