Label Propagation Rounds

Problem

Count the synchronous rounds label propagation needs until labels stop changing.

Every node starts with its own index as its label; each round each node adopts the most frequent label among its neighbors, ties going to the smallest label, while isolated nodes keep their label. If labels change every round for 100 rounds return -1, otherwise return the number of rounds performed including the final stable one. edges is a list of [u, v] pairs.

Hint

Bipartite graphs tend to oscillate forever, so the round cap matters.

Test cases

case 1

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

expected: 3

case 2

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

expected: -1

case 3

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

expected: 3

case 4

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

expected: 4

case 5

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

expected: -1

Starter codePython

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

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