Bipartite Double Cover

Problem

Build the bipartite double cover of an undirected graph with n nodes.

The cover has 2n nodes: (v, 0) and (v, 1) for every v. Each original edge u-v becomes edges between (u, 0) and (v, 1), and between (u, 1) and (v, 0). Number the cover nodes as v and n + v. Return the sorted adjacency lists of the 2n cover nodes. edges is a list of [u, v] pairs.

Hint

The double cover is always bipartite, split by the second coordinate.

Test cases

case 1

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

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

case 2

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

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

case 3

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

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

Starter codePython

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

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