Ex8-4 匯點問題
« 問題描述：
采用鄰接矩陣表示一個具有n 個頂點的圖時，大多數關于圖的算法時間復雜性為
O(n2 )，但也有例外。例如，即使采用鄰接矩陣表示一個有向圖G，確定G 是否含有一個
匯（即入度為n-1，出度為0 的頂點），只需要O(n)計算時間。試寫出其算法。
« 編程任務：
對于給定的有n個頂點的圖G 的鄰接矩陣，各頂點依次編號為1，2，…，n。試設計一
個O(n)時間算法，計算圖G 的匯點。
« 數據輸入：
由文件input.txt提供輸入數據。文件的第1 行有1 個正整數n，表示圖G 中頂點個數。
第2 行起每行n個數，共n行，給出圖G 的鄰接矩陣。
« 結果輸出:
程序運行結束時，將計算出的匯點編號輸出到output.txt中。當圖G 沒有匯點時輸出0。
輸入文件示例 輸出文件示例
input.txt
5
0 0 1 1 1
1 0 1 1 1
0 0 0 0 0
1 0 1 1 1
0 1 1 0 0
output.txt
3
標簽：
laquo
Ex
矩陣表示
上傳時間：
2013-12-25
上傳用戶：yyyyyyyyyy
