#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/euler-paths-and-circuits/teleporters-path-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/euler-paths-and-circuits/teleporters-path-implementation

Repovive

Teleporters Path - Implementation - Euler Paths and Circuits | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

Teleporters Path - Implementation

Code walkthrough.

function teleportersPath(n, edges):
    inDeg = array of 0s
    outDeg = array of 0s
    adj = adjacency list

    for each edge (u, v):
        outDeg[u] = outDeg[u] + 1
        inDeg[v] = inDeg[v] + 1
        adj[u].append(v)

        // Check conditions
        if outDeg[1] != inDeg[1] + 1:
            return "IMPOSSIBLE"
    if inDeg[n] != outDeg[n] + 1:
        return "IMPOSSIBLE"
    for v from 2 to n-1:
        if inDeg[v] != outDeg[v]:
            return "IMPOSSIBLE"

    // Run Hierholzer from vertex 1
    return hierholzer(adj, 1)

This runs in $O(E)$ time and uses $O(E)$ space.