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

Input

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

Output

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

Sample Input

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

Sample Output

v1 v3 v2 v6 v4 v5

在輸入時記錄每一個的度，然后通過度為0，不斷存儲，不斷的減度；

#include <bits/stdc++.h> using namespace std; const int maxn = 100+5; int Map[maxn][maxn]; int rudu[maxn]; int path[maxn]; int n,m; void topsort() {for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)if(Map[i][j] == 1)rudu[j]++;//表示到第j有多少個前提；for(int i = 1; i <= n; i++){int item = 0;for(int j = 1; j <= n; j++)if(rudu[j]==0)//表示到達該點的前提沒了{item = j;break;}rudu[item] = -1; //更新為-1path[i] = item;for(int j = 1; j <= n; j++)if(Map[item][j] == 1)rudu[j]--;} } int main() {while(scanf("%d%d",&n,&m)==2){int a,b;memset(Map,0,sizeof Map);memset(rudu,0,sizeof rudu);memset(path,0,sizeof path);for(int i = 1; i <= m; i++){scanf("%d %d",&a,&b);Map[a][b] = 1;//表示a->b的一個關(guān)系；}topsort();for(int i = 1; i < n; i++)printf("v%d ",path[i]);printf("v%d\n",path[n]);}return 0; }

?

總結(jié)

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

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