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)