Adjacency List to Edge List

Problem

Convert an undirected adjacency list back into a sorted edge list.

adj[u] lists the neighbors of node u and the representation is symmetric. Return every edge once as [u, v] with u < v, sorted in ascending order. Isolated nodes simply contribute no edges.

Hint

Keep only the direction where u is smaller than v to avoid listing each edge twice.

Test cases

case 1

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

expected: [[0,1]]

case 2

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

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

case 3

in: [[[],[],[]]]

expected: []

case 4

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

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

Starter codePython

def adjacency_list_to_edges(adj):
    # Your code here
    pass

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