K-Core Numbers

Problem

Compute the core number of every node in an undirected graph: the largest k such that the node belongs to the k-core, the maximal subgraph with all degrees at least k.

Repeatedly remove the node with the smallest current degree; its core number is that degree when removed. Return the core numbers in node order.

Hint

Peel away the current minimum-degree node and decrease its neighbors' degrees.

Test cases

case 1

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

expected: [2,2,2,1]

case 2

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

expected: [3,3,3,3]

case 3

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

expected: [1,1,1]

case 4

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

expected: [1,1,1,1]

case 5

in: [3,[]]

expected: [0,0,0]

Starter codePython

import heapq
def k_core_numbers(n, edges):
    # Your code here
    pass

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