2,026 views
1 votes
1 votes
Ms. Dany wants to clean the house having many rooms. She moves from one room to the next which takes 1 time unit. Each room has only one exit door. After some time she is bound to reach a room which she has cleaned already. Let the time taken to reach the already traversed room be 't' from the start. After that shes enters a cycle, let the length in the cycle be 'k'. Print 't' and 'k'.(do not condiser time taken to clean the room) (Hint : DFS)

1 Answer

0 votes
0 votes

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)
   }
    
}
edited by

Related questions

1 votes
1 votes
1 answer
1
pC asked Jul 18, 2016
1,245 views
Implement Longest Increasing Subsequence with the help of 1-D array for dynamic programming. (Hint : MaxTill 1-D array)
1 votes
1 votes
1 answer
2
pC asked Jul 18, 2016
1,367 views
Implement a^b mod m where a,b and m can be huge. (Hint : O(log n))
0 votes
0 votes
1 answer
3
itachi asked May 9, 2017
695 views
In which segment of memory layout the information about dynamic linked libraries is stored?