Ear Decomposition Step

Problem

Find one ear to extend a cycle in an undirected graph.

An ear is a path whose endpoints lie on the given cycle and whose internal nodes lie outside it. Scan the edges in input order for the first edge crossing from the cycle to outside, then DFS through outside nodes until reaching a different cycle node. Return the ear path from one cycle endpoint to the other, or [] when no ear exists. cycle is a list of distinct cycle nodes.

Hint

Ear decomposition builds any 2-connected graph from a cycle by adding ears.

Test cases

case 1

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

expected: [2,3,0]

case 2

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

expected: [2,3,0]

case 3

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

expected: []

Starter codePython

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

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