Round Trip - Implementation

Pattern: DFS cycle detection in undirected graph.

function roundTrip(n, adj):
    visited = array of size n + 1, all false
    parent = array of size n + 1, all -1
    cycleStart = -1
    cycleEnd = -1

    function dfs(u, p):
        visited[u] = true
        parent[u] = p
        for v in adj[u]:
            if v == p:
                continue
            if visited[v]:
                cycleStart = v
                cycleEnd = u
                return true
            if dfs(v, u):
                return true
        return false

    for i from 1 to n:
        if not visited[i]:
            if dfs(i, -1):
                path = reconstructCycle(parent, cycleStart, cycleEnd)
                print path.length
                print path
                return

    print "IMPOSSIBLE"

Time: $O(N + M)$. Space: $O(N)$.