Onion Decomposition Lite

Problem

Compute the onion layer of every node of an undirected graph.

Layer 1 is the set of nodes with minimum current degree removed all at once; then update degrees and repeat, recording the layer number when each node is removed. Return the layer list in node order. edges is a list of [u, v] pairs.

Hint

Onion layers peel all minimum-degree nodes at once, unlike one-at-a-time k-core peeling.

Test cases

case 1

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

expected: [2,1,1,1]

case 2

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

expected: [1,1,1,1]

case 3

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

expected: [1,2,2,1]

case 4

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

expected: [2,2,2,1]

case 5

in: [2,[]]

expected: [1,1]

Starter codePython

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

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