Independent Set Greedy by Degree

Problem

Build an independent set greedily by always taking the highest-degree remaining node.

Pick the remaining node with the largest current degree (ties broken by smallest index), add it, and delete it together with all of its neighbors. Return the number of chosen nodes. edges is a list of [u, v] pairs.

Hint

Removing a high-degree node also removes many conflicts at once.

Test cases

case 1

in: [4,[[0,1],[0,2],[0,3]]]

expected: 1

case 2

in: [4,[[0,1],[1,2],[2,3]]]

expected: 2

case 3

in: [4,[[0,1],[0,2],[0,3],[1,2],[1,3],[2,3]]]

expected: 1

case 4

in: [3,[]]

expected: 3

case 5

in: [3,[[0,1],[1,2],[2,0]]]

expected: 1

Starter codePython

def independent_set_by_degree(n, edges):
    # Your code here
    pass

5 test cases · run your code against them in the editor