Ex8-4 匯點(diǎn)問題 « 問題描述： 采用鄰接矩陣表示一個(gè)具有n 個(gè)頂點(diǎn)的圖時(shí)，大多數(shù)關(guān)于圖的算法時(shí)間復(fù)雜性為 O(n2 )，但也有例外。例如，即使采用鄰接矩陣表示一個(gè)有向圖G，確定G 是否含有一個(gè) 匯（即入度為n-1，出度為0 的頂點(diǎn)），只需要O(n)計(jì)算時(shí)間。試寫出其算法。 « 編程任務(wù)： 對(duì)于給定的有n個(gè)頂點(diǎn)的圖G 的鄰接矩陣，各頂點(diǎn)依次編號(hào)為1，2，…，n。試設(shè)計(jì)一 個(gè)O(n)時(shí)間算法，計(jì)算圖G 的匯點(diǎn)。 « 數(shù)據(jù)輸入： 由文件input.txt提供輸入數(shù)據(jù)。文件的第1 行有1 個(gè)正整數(shù)n，表示圖G 中頂點(diǎn)個(gè)數(shù)。 第2 行起每行n個(gè)數(shù)，共n行，給出圖G 的鄰接矩陣。 « 結(jié)果輸出: 程序運(yùn)行結(jié)束時(shí)，將計(jì)算出的匯點(diǎn)編號(hào)輸出到output.txt中。當(dāng)圖G 沒有匯點(diǎn)時(shí)輸出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

點(diǎn)擊標(biāo)簽查看更多相關(guān)資源：