HDU 4857 逃生（拓撲排序）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 拓撲排序

一.定義

??? 對一個有向無環圖(Directed Acyclic Graph簡稱DAG)G進行拓撲排序，是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若<u，v> ∈E(G)，則u在線性序列中出現在v之前。

?? 通常，這樣的線性序列稱為滿足拓撲次序(Topological Order)的序列，簡稱拓撲序列。

?? 注意:

?? 1)只有有向無環圖才存在拓撲序列;

?? 2)對于一個DAG,可能存在多個拓撲序列（此題已經規定了數字的優先級，所以答案唯一）;

?

二.拓撲序列算法思想

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

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

重復上述兩步，直至圖空，或者圖不空但找不到無前驅的頂點為止。

#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;
}

?