HDU 1285 確定比賽名次（拓撲排序模板）
題意還是比較容易理解的，關鍵要看到後面的：合條件的排名可能不是唯一的，此時要求輸出時編號小的隊伍在前；
思路：這道題就是拓撲排序的經典應用了，用隊列做的考慮優先編號小的出隊就可以了。
拓撲排序：
拓撲排序是對有向無回路圖(DAG)頂點的一種排序，它使得如果存在從u到v的有向路徑，那麼滿足序列中u在v前。
所以我們的算法可以描述為這樣一個過程：
1、找到整個圖中所有的度為0的點，將這些點壓進隊列（棧）中
2、從隊列（棧）中取出一點，輸出，將該點及它的邊刪除，找到它所指向的點，如果改點是一個原點（刪除指向它的點後），則壓入隊列（棧）
3、重復2過程，直到它為空
注：所謂度為0，即沒有子節點，為1則只有一個，為2則有2個。為什麼要先讓度為0的點出來？因為你在定義的時候，度為0的點，則說明其沒有父節點，即沒有人排在它的前面！
所以基本AC代碼：
#include
#include
using namespace std;
int map[502][502],flag[502],m,n,val[502];
void topsort()
{
int i, j, k=1;
for(i=1; i<=n; i++) //有n個點，所以要找n次
{
for(j=1; j<=n; j++)
{
if(flag[j]==0) //循環尋找度為0的點
{
flag[j]--;
val[k++]=j;
for(int x=1; x<=n; x++) //刪除指向該點的邊
if(map[j][x])
flag[x]--; //使其度為0
break;
}
if(j>n)
return ;
}
}
}
int main()
{
int i,j;
while(cin>>n>>m)
{
memset(map,0,sizeof(map));
memset(flag,0,sizeof(flag)); //初始化所有的點的度為0
int a,b;
for(i=1;i<=m;i++)
{
cin>>a>>b;
if(!map[a][b])
{
map[a][b]=1;
flag[b]++; //度增加
}
}
topsort();
for(i=1;i<=n; i++)
if(i!=n)
cout<
優先隊列優化後的代碼：
#include
#include
#include
#include
#include
using namespace std;
const int N=510+10;
vector g[N]; //鄰接表
int du[N],val[N];
int n,m;
void topsort()
{
int i;
priority_queue, greater > q;//定義一個優先隊列，並定義編號小的優先出隊
for(i=1;i<=n;i++)
if(!du[i])
q.push(i);
int cnt=1;
while(!q.empty())
{
int u=q.top();
q.pop();
val[cnt++]=u;
for(i=0;i
