We can model this as a graph. Each room is a vertex. She travels from vertex to another along a edge of weight 1 (1 is the time taken to travel a vertex). Now suppose she visits a vertex vi at time t and then she goes to room vj, then the time at which she visits vj is t+1. Further if she visits a sequence of vertices v1,v2,..,vk in that order and time of visit of v1 is t1 and time of visit of vk is tk, then the number of edges she has visited while traversing from v1 to vk is tk - t1.
G is a graph having n vertices connected by edges
time[n] is a global array indicating most recent time of visit of each vertex.
time[i] = -1 indicates that the ith vertex is not visited yet
start_vertex denotes the vertex from which we start the dfs.
cycleLength[n] is a global array
cycleLength[i] indicates the length of the cycle we have encountered starting and ending at ith vertex while traversing the graph.
cycleLength[i] = 0 for all vetex i initially
currentTime is a static variable and incremented each time we visit a node. currentTime = -1 initially.
DFS(G,start_vertex) {
// increment currentTime
currentTime = currentTime + 1
// is the start_vertex already visited ? Then we have a cycle
if(time[start_vertex] != -1) {
// time taken to reach the already traversed room be 't' from the start.
//So t = time[start_vertex]
t = time[start_vertex]
// Cycle length k
cycleLength[start_vertex] = currentTime - time[start_vertex]
// Update time[start_vertex]
time[start_vertex] = currentTime
// Print result.
print ("Vertex " + start_vertex + " initially visited at time " + t +
" is now visited again, with cycle length " + cycleLength[start_vertex] )
}
else { // first visit
time[start_vertex] = currentTime
}
for each vertex v adjacent to start_vertex {
// perform dfs on each adjacent vertex
// we are allowed to visit the same vertex again. So no need to check if it is visited
DFS(G,v)
}
}