1707 問題 C: 數(shù)據(jù)結(jié)構(gòu)-有向無環(huán)圖的拓撲排序
時間限制: 1s
內(nèi)存限制: 32MB 提交: 521 解決: 154
題目描述
由某個集合上的一個偏序得到該集合上的一個全序，這個操作被稱為拓撲排序。偏序和全序的定義分別如下：
若集合X上的關系R是自反的、反對稱的和傳遞的，則稱R是集合X上的偏序關系。
設R是集合X上的偏序，如果對每個x,y∈X必有xRy或yRx，則稱R是集合X上的全序關系。
由偏序定義得到拓撲有序的操作便是拓撲排序。
拓撲排序的流程如下：
1. 在有向圖中選一個沒有前驅(qū)的頂點并且輸出之；
2. 從圖中刪除該頂點和所有以它為尾的弧。
重復上述兩步，直至全部頂點均已輸出，或者當前圖中不存在無前驅(qū)的頂點為止。后一種情況則說明有向圖中存在環(huán)。
采用鄰接表存儲有向圖，并通過棧來暫存所有入度為零的頂點，可以描述拓撲排序的算法如下：
在本題中，讀入一個有向圖的鄰接矩陣（即數(shù)組表示），建立有向圖并按照以上描述中的算法判斷此圖是否有回路，如果沒有回路則輸出拓撲有序的頂點序列。
輸入
輸入的第一行包含一個正整數(shù)n，表示圖中共有n個頂點。其中n不超過50。
以后的n行中每行有n個用空格隔開的整數(shù)0或1，對于第i行的第j個整數(shù)，如果為1，則表示第i個頂點有指向第j個頂點的有向邊，0表示沒有i指向j的有向邊。當i和j相等的時候，保證對應的整數(shù)為0。
輸出
如果讀入的有向圖含有回路，請輸出“ERROR”，不包括引號。
如果讀入的有向圖不含有回路，請按照題目描述中的算法依次輸出圖的拓撲有序序列，每個整數(shù)后輸出一個空格。
請注意行尾輸出換行。
樣例輸入
4 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0
樣例輸出
3 0 1 2
提示
比賽公告
暫無……