想问一下交大 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

想请问交大的考古题去哪里下载？感谢。