Software Engineer

DFS can be used to detect cycle in an undirected graph. Do a DFS traversal of the given graph. For every visited vertex ‘v’, if there is an adjacent ‘u’ such that u is already visited and u is not parent of v, then there is a cycle in graph.

If we don’t find such an adjacent for any vertex, we say that there is no cycle.

Pseudocode :

DetectCycle(graph, v, visited[], parent)
{
	// mark the current node as visited
	visited[v] = true;
	// do for every edge (v, w)
	for (w: graph[v])
	{
		// if `w` is not visited yet
		if (!visited[w])
		{
			if (DetectCycle(graph, w, visited, v)) {
				return true;
			}
		}
		// if `w` is visited, and `w` is not a parent
		else if (w != parent)
		{
			// back-edge (cycle) found
			return true;
		}
	} 
	// No back-edges were found in the graph
	return false;
}

One method could be to divide the array in slots of size n/3. A simple way to implement 3 stacks is to divide the array in 3 slots of size n/3 each, and fix the slots for different stacks, i.e., use arr[0] to arr[n/3-1] for first stack, and arr[n/3] to arr[2n/3-1] for stack2 where arr[] is the array to be used to implement 3 stacks and size of array be n. The problem with this method is inefficient use of array space. A stack push operation may result in stack overflow even if there is space available in arr[].

A space efficient implementation : The idea is to use two extra arrays for efficient implementation of 3 stacks in an array. 
Following are the two extra arrays are used :
1) top[]: This is of size 3 and stores indexes of top elements in all stacks.
2) next[]: This is of size n and stores indexes of next item for the items in array arr[]. Here arr[] is actual array that stores 3 stacks.
Together with 3 stacks, a stack of free slots in arr[] is also maintained. The top of this stack is stored in a variable ‘free’.
All entries in top[] are initialized as -1 to indicate that all stacks are empty. All entries next[i] are initialized as i+1 because all slots are free initially and pointing to next slot. Top of free stack, ‘free’ is initialized as 0.

1. A compiled language is a programming language whose implementations are typically compilers and not interpreters. An interpreted language is a programming language whose implementations execute instructions directly and freely, without previously compiling a program into machine-language instructions.

2. In compiled language, once the program is compiled it is expressed in the instructions of the target machine. While in interpreted language, the instructions are not directly executed by the target machine.
 

3. In compiled language, there are at least two steps to get from source code to execution. In interpreted language, there is only one step to get from source code to execution.
 

4. In compiled language, compiled programs run faster than interpreted programs. While in interpreted language, interpreted programs can be modified while the program is running.
 

5. In compiled language, compilation errors prevent the code from compiling. In interpreted language, all the debugging occurs at run-time.