Maximum Independent Set Greedy Method 如下:
Greedy(G):
S = {}
While G is not empty:
Let v be a node with minimum degree in G // 選擁有最小 degree 的點
S = union(S, {v})
remove v and its neighbors from G // 將選到的點和它的鄰居刪掉
return S

如果有題址我會去衝的。

priority queue欸 不對 這樣會跟邊數相關還是n^2如果E<<V^2的話就是拔點的時候把鄰居degree-1丟進去可以做到O(E log V) 我猜可能可以再壓到O(E)要比O(E)再低可能就不是很合理啦 畢竟圖大小就那樣了每個degree建個list(vector) 點丟到list裡刪點的時候把鄰居degree-1，丟到他該去的list裡維護當前最小degree值 刪點頂多-1 所以至多回退V每個點只會出現在(移除時degree~原degree)的lsit中總數O(E) 所以整體來說應該是O(E)