題目 1707:
數(shù)據(jù)結(jié)構(gòu)-有向無(wú)環(huán)圖的拓?fù)渑判?/h1>
時(shí)間限制: 2s
內(nèi)存限制: 96MB 提交: 521 解決: 154
題目描述
由某個(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序，這個(gè)操作被稱(chēng)為拓?fù)渑判?。偏序和全序的定義分別如下：
若集合X上的關(guān)系R是自反的、反對(duì)稱(chēng)的和傳遞的，則稱(chēng)R是集合X上的偏序關(guān)系。
設(shè)R是集合X上的偏序，如果對(duì)每個(gè)x,y∈X必有xRy或yRx，則稱(chēng)R是集合X上的全序關(guān)系。
由偏序定義得到拓?fù)溆行虻牟僮鞅闶峭負(fù)渑判颉?
拓?fù)渑判虻牧鞒倘缦拢?
1. 在有向圖中選一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)并且輸出之；
2. 從圖中刪除該頂點(diǎn)和所有以它為尾的弧。
重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出，或者當(dāng)前圖中不存在無(wú)前驅(qū)的頂點(diǎn)為止。后一種情況則說(shuō)明有向圖中存在環(huán)。
采用鄰接表存儲(chǔ)有向圖，并通過(guò)棧來(lái)暫存所有入度為零的頂點(diǎn)，可以描述拓?fù)渑判虻乃惴ㄈ缦拢?
在本題中，讀入一個(gè)有向圖的鄰接矩陣（即數(shù)組表示），建立有向圖并按照以上描述中的算法判斷此圖是否有回路，如果沒(méi)有回路則輸出拓?fù)溆行虻捻旤c(diǎn)序列。
輸入格式
輸入的第一行包含一個(gè)正整數(shù)n，表示圖中共有n個(gè)頂點(diǎn)。其中n不超過(guò)50。
以后的n行中每行有n個(gè)用空格隔開(kāi)的整數(shù)0或1，對(duì)于第i行的第j個(gè)整數(shù)，如果為1，則表示第i個(gè)頂點(diǎn)有指向第j個(gè)頂點(diǎn)的有向邊，0表示沒(méi)有i指向j的有向邊。當(dāng)i和j相等的時(shí)候，保證對(duì)應(yīng)的整數(shù)為0。
輸出格式
如果讀入的有向圖含有回路，請(qǐng)輸出“ERROR”，不包括引號(hào)。
如果讀入的有向圖不含有回路，請(qǐng)按照題目描述中的算法依次輸出圖的拓?fù)溆行蛐蛄校總€(gè)整數(shù)后輸出一個(gè)空格。
請(qǐng)注意行尾輸出換行。
樣例輸入
4 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0
樣例輸出
3 0 1 2
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情