416
技術社區[雲棲]
【算法小總結】拓撲排序+例題解析
題目1449：確定比賽名次
時間限製：1 秒內存限製：128 兆特殊判題：否提交：669解決：293
題目描述：
有N個比賽隊（1<=N<=500），編號依次為1，2，3，。。。。，N進行比賽，比賽結束後，裁判委員會要將所有參賽隊伍從前往後依次排名，但現在裁判委員會不能直接獲得每個隊的比賽成績，隻知道每場比賽的結果，即P1贏P2，用P1，P2表示，排名時P1在P2之前。現在請你編程序確定排名。
輸入：
輸入有若幹組，每組中的第一行為二個數N（1<=N<=500），M；其中N表示隊伍的個數，M表示接著有M行的輸入數據。接下來的M行數據中，每行也有兩個整數P1，P2表示即P1隊贏了P2隊。
輸出：
給出一個符合要求的排名。輸出時隊伍號之間有空格，最後一名後麵沒有空格。
其他說明：符合條件的排名可能不是唯一的，此時要求輸出時編號小的隊伍在前；輸入數據保證是正確的，即輸入數據確保一定能有一個符合要求的排名。
樣例輸入：
4 3
1 2
2 3
4 3
樣例輸出：
1 2 4 3
//拓撲排序
/*拓撲排序方法如下:
(1)從有向圖中選擇一個沒有前驅(即入度為0)的頂點並且輸出它.
(2)從網中刪去該頂點,並且刪去從該頂點發出的全部有向邊.
(3)重複上述兩步,直到剩餘的網中不再存在沒有前趨的頂點為止.*/
#include<stdio.h>
#include<string.h>
int degree[510],bin[510],map[510][510];
void ToPu(int n)
{
int i,j,p;
for(i=1;i<=n;i++)
{
p=-1;//用來記錄入度為0的結點
for(j=1;j<=n;j++)
{
if(degree[j]==0)//如果入度為0
{
degree[j]--;//讓他為負數
bin[i]=p=j;
break;//找到那個入度為0的結點，說明他是本組查找的元老
}
}
for(j=1;j<=n;j++)
{
if(map[p][j]==1)//去掉p鏈接的所有路
{
map[p][j]=0;
degree[j]--;//j的入度減去1
}
}
}
}
int main()
{
int i,j,n,m,x,y;
while(scanf("%d %d",&n,&m)!=EOF)
{
memset(degree,0,sizeof(degree));
memset(bin,0,sizeof(bin));
memset(map,0,sizeof(map));
for(i=0;i<m;i++)
{
scanf("%d %d",&x,&y);
if(map[x][y]==0)
{
map[x][y]=1;
degree[y]++;//y點的入度加一
}
}
ToPu(n);
printf("%d",bin[1]);
for(i=2;i<=n;i++)
printf(" %d",bin[i]);
puts("");
}
return 0;
}
因為每次都要搜索入度為0的節點，花費的時間是O(n^2)
可以進行優化到O(E+V)
優化思想，可以通過將所有（未分配拓撲編號）入度為0的頂點放在一個特殊的盒子中而避免
這種無效的勞動。當降低鄰接頂點的入度的時候，檢查每一個頂點並在他入度為0的時候把它放入盒子。
步驟：
1.對每一個頂點計算它的入度，將所有入度為0的頂點放入一個初始為空的隊列中。
2.當隊列不空時，刪除一個頂點v，並將與v鄰接的所有的頂點的入度減1。
3.在剛剛的操作中，隻要有一個頂點的入度降為0，就把該頂點放入隊列中。
此時，拓撲排序就是頂點出隊的順序。
優化代碼：
//注意，這個寫法是沒要求輸出時編號小的隊伍在前
//寫這個的目的是清楚優化的方法，不是為此題而編寫
void ToPu(int n)
{
queue<int> q;
int sum=1;
int v,i;
while(!q.empty()){q.pop();}
for(i=1;i<=n;i++)
if(degree[i]==0)
q.push(i);
while(!q.empty())
{
v=q.front();
q.pop();
bin[sum++]=v;
for(i=1;i<=n;i++)
{
if(map[v][i]==1)
{
degree[i]--;
if(degree[i]==0)
q.push(i);
}
}
}
}
最後更新：2017-04-03 05:39:37