Line Graph Build

Problem

Build the line graph of an undirected graph: every original edge becomes a node, and two line-graph nodes are adjacent when the original edges share exactly one endpoint.

edges is the original list of [u, v] pairs. Return the sorted adjacency lists of the line graph, whose node count is len(edges).

Hint

Edges sharing two endpoints are parallel edges and do not create line-graph adjacency here.

Test cases

case 1

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

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

case 2

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

expected: [[],[]]

case 3

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

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

case 4

in: [[[0,1]]]

expected: [[]]

Starter codePython

def line_graph(edges):
    # Your code here
    pass

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