當(dāng)用鄰接矩陣表示時(shí)，大多數(shù)算法需要的時(shí)間都是O(V
2)的，但有一些例外
證明：在給定一有向圖有向圖G的鄰接矩陣后，可以在O(V)的時(shí)間內(nèi)確定G中是否含一個(gè)“通用的匯(universal sink),即入度為|V|-1，出度為0的頂點(diǎn)。
感覺這題挺有意思，自己想了半天，大概想出了方法，不過有點(diǎn)懷疑正確性，所以GOOGLE了一下
后來發(fā)現(xiàn)這還是YAHOO二面的一個(gè)題...（P.S.美國(guó)雅虎）
圖上畫畫就會(huì)發(fā)現(xiàn)，這樣的圖都很有型....
eg.
G:
1 2 3 4
10 1
2 0 1
30 0 0 0
4 1 0
對(duì)角線都是0，而是sink的點(diǎn)，橫著豎著剛好組成個(gè)十字。
while(j<n)
{
if(G[i,j]=0)
j++;
else
i++;
}
return i;
所以只需要找到十字是在哪個(gè)點(diǎn)就成了。這么掃一遍復(fù)雜度為O(V)。但有點(diǎn)小問題，如果不是的話，可能返回其它值
eg.
G:
1 2 3 4
1 0 0 1 0
2 1 0 0 0
3 1 1 0 1
4 1 0 1 0
這個(gè)的話就會(huì)返回2，顯然2不是universal sink
所以需要得到答案后再驗(yàn)證一下這個(gè)點(diǎn)，橫掃豎掃，同樣，復(fù)雜度也控制在O(V)
順便，贊一下國(guó)外論壇的討論氛圍。
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1195383906另貼一個(gè)網(wǎng)上找的本題的解法
http://www.csie.ntu.edu.tw/~r95122/alg07spr/alg07spr_hw1sol.pdf