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: . Space: .