FastPrepCanonical Euler Trail

Canonical Euler Trail

Wells Fargo logoWells Fargo● HardINTERNOA
Learn

Problem statement

You are given a connected undirected multigraph with vertices numbered from 1 through n. Edge i joins edgeFrom[i] and edgeTo[i]. Parallel edges are allowed.

The graph is guaranteed to have an Euler trail: a vertex sequence that uses every edge exactly once. Return the trail produced by this canonical Hierholzer order:

  1. If exactly two vertices have odd degree, start at the smaller one. Otherwise start at the smallest vertex incident to an edge.
  2. Whenever the traversal is at a vertex, consume the unused incident edge whose other endpoint is smallest. If several such edges have the same endpoint, consume the one with the smallest input index.
  3. Use Hierholzer backtracking and reverse the completed postorder sequence.

Function

canonicalEulerTrail(n: int, edgeFrom: int[], edgeTo: int[]) → int[]

Examples

Example 1

n = 3edgeFrom = [1,2]edgeTo = [2,3]return = [1,2,3]

The only Euler trail starts at odd-degree vertex 1 and follows both edges.

Example 2

n = 3edgeFrom = [1,2,3]edgeTo = [2,3,1]return = [1,2,3,1]

All degrees are even, so traversal starts at vertex 1 and takes neighbor 2 first.

Example 3

n = 4edgeFrom = [1,1,2,3]edgeTo = [2,3,4,4]return = [1,2,4,3,1]

Vertices 1 and 4 are odd; start at 1 and consume the edge to 2 before the edge to 3.

Constraints

  • 2 <= n <= 10^5.
  • 1 <= edgeFrom.length == edgeTo.length <= 2 * 10^5.
  • Every endpoint is between 1 and n, and no edge is a self-loop.
  • The graph is connected after ignoring isolated vertices and has either zero or two odd-degree vertices.
  • Every vertex from 1 through n is incident to at least one edge.

More Wells Fargo problems

See Wells Fargo hiring insights
public int[] canonicalEulerTrail(int n, int[] edgeFrom, int[] edgeTo) {
  // write your code here
}
n3
edgeFrom[1,2]
edgeTo[2,3]
expected[1,2,3]
Checking account…