Graph Quotient Contraction Step

Problem

Build the quotient graph obtained by contracting nodes that share a group label.

groups[v] is the supernode label of node v. Collect all edges between different groups, deduplicate them, drop self-loops, and return them as a sorted list of [a, b] pairs with a < b. edges is a list of [u, v] pairs.

Hint

Contraction replaces each group by a supernode and keeps inter-group links.

Test cases

case 1

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

expected: [[0,1]]

case 2

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

expected: []

case 3

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

expected: [[0,1]]

Starter codePython

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

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