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