想問一下交大 109 資演的兩題
第一題是判斷一個具有 n 個 node 的圖是否為 2-colorable 的演算法的時間複雜度
https://imgur.com/17RaKhB
答案是 (B) O(n^2)，但我選 (A) O(n)
原因是因為我覺得只要 traverse 一遍圖上的每一個點，
就可以判斷是否為 2-colorable 了
後來查了一下發現這個網站（https://pse.is/38yh5r）
說可以用 BFS 判斷是否為 2-colorable
時間複雜度為 O(V+E)
所以我覺得好奇怪，是我哪裡理解錯了嗎？還是答案錯了？
https://imgur.com/89Kkx4y

我想第一題的BFS應該是用adjacency matrix因為選項裡都沒有跟edge有關用adjacency list才會是你說的O(V+E)adjacency matrix的話就是O(V^2)

哦哦哦！我懂了 感謝！那如果用 adjacency list 的話，是不是可以這樣想因為一個圖最多有 V*(V-1)/2 個 edge所以O(V+E)=O(V^2)，所以用adjacency list還是O(V^2)

雖然這樣看不直觀但推導沒錯

V+E對V來說是V^2

想請問交大的考古題去哪裡下載？感謝。