題目鏈接：http://bailian.openjudge.cn/practice/4084/

總時間限制:?1000ms?內(nèi)存限制:?65536kB描述

給出一個圖的結(jié)構(gòu)，輸出其拓撲排序序列，要求在同等條件下，編號小的頂點在前。

輸入

若干行整數(shù)，第一行有2個數(shù)，分別為頂點數(shù)v和弧數(shù)a，接下來有a行，每一行有2個數(shù)，分別是該條弧所關(guān)聯(lián)的兩個頂點編號。
v<=100, a<=500

輸出

若干個空格隔開的頂點構(gòu)成的序列(用小寫字母)。

樣例輸入

6 8 1 2 1 3 1 4 3 2 3 5 4 5 6 4 6 5

樣例輸出

v1 v3 v2 v6 v4 v5

這道題可以考慮使用優(yōu)先隊列。下面的代碼偷懶，直接使用最簡單粗暴的方法：

1 #include<stdio.h> 2 #include<iostream> 3 #include<stdlib.h> 4 #include<string.h> 5 #include<algorithm> 6 using namespace std; 7 8 #define maxN 1000 9 #define maxM 2000 10 11 struct NODE 12 { 13 int from; //邊的起點 14 int to; //邊的終點 15 }; 16 struct NODE edge[maxM]; //邊數(shù)組 17 int head[maxN]; //存儲出發(fā)點為 Vi 的第一條邊在 edge[ ]中的位置，一般初始化為-1。 18 19 int n,m;//n個點m條邊的圖 20 int indegree[maxN]; 21 int ttt; 22 23 bool cmp(NODE a,NODE b) 24 { 25 if(a.from==b.from)return a.to<b.to; 26 return a.from<b.from; 27 } 28 void topo_sort();//利用隊列完成無前驅(qū)節(jié)點優(yōu)先的拓撲排序. 編號小的節(jié)點優(yōu)先輸出. 29 int main(int argc, char *argv[]) 30 { 31 int i; 32 33 34 scanf("%d%d",&n,&m); 35 for(i=0;i<m;i++) cin>>edge[i].from>>edge[i].to; 36 sort(edge,edge+m,cmp); 37 //for(i=0;i<m;i++) printf("%d %d\n",edge[i].from,edge[i].to);//測試代碼 38 memset(head,-1,sizeof(head)); 39 head[edge[0].from]=0; 40 indegree[edge[0].to]=1; 41 for(i=1;i<m;i++) 42 { 43 if(edge[i].from != edge[i-1].from) 44 { 45 head[edge[i].from]=i;//標(biāo)記以第 i 個點做起點的第一條邊在 edge[]的位置 46 } 47 indegree[edge[i].to]++;//記錄各個頂點的入度 48 } 49 //for(i=1;i<=n;i++) printf("%d ",indegree[i]); printf("\n"); //測試代碼：輸出各個點的入度.(題目數(shù)據(jù)頂點編號從1開始） 50 51 topo_sort(); 52 53 return 0; 54 } 55 56 void topo_sort()//利用隊列完成無前驅(qū)節(jié)點優(yōu)先的拓撲排序. 編號小的節(jié)點優(yōu)先輸出. 57 { 58 int i,k; 59 ttt=n; 60 while(ttt>0) 61 { 62 for(i=1;i<=n;i++)//掃描尋找編號最小的無前驅(qū)節(jié)點 63 { 64 if(indegree[i]==0) 65 { 66 printf("v%d ",i); 67 ttt--; 68 if(head[i]!=-1)//該頂點有鄰接點 69 { 70 //遍歷該頂點出發(fā)的全部有向邊,把這些邊的終點的入度減1. 71 for(k=head[i];edge[k].from==i&&k<m;k++) 72 { 73 indegree[edge[k].to]--; 74 } 75 head[i]=-1;//刪除該頂點出發(fā)的全部有向邊 76 } 77 indegree[i]=-1; 78 break; 79 } 80 } 81 } 82 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/huashanqingzhu/p/9291886.html

總結(jié)

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

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