GATE CSE 1992 | Question: 8

Question

Let $T$ be a Depth First Tree of a undirected graph $G$. An array $P$ indexed by the vertices of $G$ is given. $P[V]$ is the parent of vertex $V$, in $T$. Parent of the root is the root itself.

Give a method for finding and printing the cycle formed if the edge $(u,v)$ of $G$ not in $T$ (i.e., $e \in G-T$) is now added to $T$.

Time taken by your method must be proportional to the length of the cycle.

Describe the algorithm in a PASCAL $(C)$ – like language. Assume that the variables have been suitably declared.

Comments

plz someone explain this....

---

@Habibkhan

---

Union find is used for the same. U may read the algo from geeksforgeeks or from somewhere else.

---

Most of the answers here, including the best answer, have understood the problem wrong. We don't have to find the cycle, it is already given that u and v are nodes that are in the cycle.

All we have to do is get all nodes from u to root, get all nodes from v to root, and remove the common part.

length of path from v->root + length from u->root is cycle length. And we can get parent of a node in O(1), so the algo works in O(cycle length)

All answers including union find/DFS are wrong, as they are O(V) is greater than the cycle length.

// Function to find and print the cycle
void findAndPrintCycle(int u, int v, int P[], int n) {
    int pathU[MAX_SIZE]; // Array to store the path from u to root
    int pathV[MAX_SIZE]; // Array to store the path from v to root
    int cycle[MAX_SIZE]; // Array to store the cycle
    int pathUSize = 0;   // Current size of pathU
    int pathVSize = 0;   // Current size of pathV
    int cycleSize = 0;   // Current size of cycle
    int current;

    // Step 1: Find the path from u to the root
    current = u;
    while (current != P[current]) {
        pathU[pathUSize++] = current;
        current = P[current];
    }
    pathU[pathUSize++] = current; // Add the root

    // Step 2: Find the path from v to the root
    current = v;
    while (current != P[current]) {
        pathV[pathVSize++] = current;
        current = P[current];
    }
    pathV[pathVSize++] = current; // Add the root

    // Step 3: Remove the common part from the paths
    while (pathUSize > 0 && pathVSize > 0 && pathU[pathUSize - 1] == pathV[pathVSize - 1]) {
        --pathUSize;
        --pathVSize;
    }

    // Step 4: Form the cycle by concatenating pathU and reversed pathV
    for (int i = 0; i < pathUSize; ++i) {
        cycle[cycleSize++] = pathU[i];
    }
    cycle[cycleSize++] = pathU[pathUSize]; // Add the last common ancestor
    cycle[cycleSize++] = v; // Add v to complete the cycle
    for (int i = pathVSize - 1; i >= 0; --i) {
        cycle[cycleSize++] = pathV[i];
    }

    // Step 5: Print the cycle
    for (int i = 0; i < cycleSize; ++i) {
        printf("%d ", cycle[i]);
    }
    printf("\n");
}

 

---

In DFS Tree of an undirected graph, if adding some edge creates a cycle then it must be a "back edge".
So u -> v is a back edge, it imples v is an ancestor of u.
Here Instead of traversing back till root, we can just traverse from u until v is found.
@dbaxi

Answer 1

Here we can run DFS on the DFS tree, to detect whether there is a cycle in O(V+E) time

Since, in a tree of n vertices, we have n-1 edges, adding a cycle will create n edges.

So, there will exist a cycle of exactly n edges when we add one edge to T.

So, now time complexity of DFS becomes, O(V+V)=O(V) which will be proportional to the length of the cycle.

Now, consider an example where we have a graph and DFS produces DFS tree for it.

And DFS tree will be

Now suppose I add a edge between 1-3 in the graph and now my algorithm would be

(1)Initialize all vertices of T to white.

Start with say 1

(2) Mark this vertex 1 with GREY color.

Now, push 1 onto stack and move to it's neighbor in T

(3)If 1's neighbor has color white(undiscovered vertex), push it onto the stack, mark it grey and now discover 2's neighbors.

(4)Then, we move to 5(white), marked grey, pushed onto stack and neighbor of 5 i.e. 4(white) being examined.

(5)4 marked greyed and pushed onto the stack.

(6) No more neighbor for 4, mark 4 as black and pop off 4 from the stack.

(7)Discovered 3 as white neighbor of 5, mark it grey and now examine all neighbor of 3.

(8)Now because of new edge added in T, vertex 1 which is grey is discovered as the neighbour of 3 and 3 is also gray.

Means we have encountered a back edge!!.

Now, return all the vertices which are in the stack and those will be the vertices which make up a cycle.

Time complexity-O(V)

Comments

WHITE : Vertex is not processed yet.  Initially
        all vertices are WHITE.

GRAY : Vertex is being processed (DFS for this 
       vertex has started, but not finished which means
       that all descendants (ind DFS tree) of this vertex
       are not processed yet (or this vertex is in function
       call stack)

BLACK : Vertex and all its descendants are 
        processed.

While doing DFS, if we encounter an edge from current 
vertex to a GRAY vertex, then this edge is back edge 
and hence there is a cycle

---

Fantastic answer by @Ayush Upadhyaya Sir.

Note: 

If Back Edge exists in DFS Traversal of Undirected/Directed Graph → There is a Cycle. [This is because tree edges are enough to complete the DFT, so adding even 1 back edge makes no. of edges = n and there is a cycle]

If Cross Edge exists in BFS Traversal of Undirected Graph → There is a Cycle [Because there are no back edges or forward edges in BFT of Undirected Graph]

If Back Edge exists in BFS Traversal of Directed Graph → There is a Cycle. 

---

@Ayush Upadhyaya sir You explained in easy and detailed manner. 

---

@Abhrajyoti00 that points are very useful bro thanks 

Answer 2

Union-Find Algorithm can be used to find the cycle.

Ref: http://www.geeksforgeeks.org/union-find/

Answer 3

Union find can take 0(logn) but we need time complexity proportional to cycle length.Lets see how we can do this:-

When we add a edge u-v ,which is in G but not int T,then cycle will come for sure as we have n edges now for n vertices.Now,if we clearly observe then we can see there are two paths now between u and v.

One is earlier path and one is the new path (by adding edge u-v).Now if we can find the earlier path between u and v ,then that path is the cycle and it will be our answer.So how to do that?

We are given with P array which is having parent of each node.Just start from node v and then get its parent say y,now goto to node y in P and get its parent .Do this until we get the node u,and keep on printing all the nodes we access.So,tis is how we get the cycle formed by adding edge u-v in o(m) time,where m is length of cycle.

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------

See the below example.I added 1-3 edges from G to T.And now start from 3 in P array and traverse till we find 1.

Note that mif the path goes from root,then we can do some modification here in constant time because if you try to get path that goes from root ,then when you reach root its parent is root only and progress cannot be made.

Comments

Just one small Note:

In the DFS tree T either u is the ancestor of v or  v is the ancestor of u , because  G has (u,v) edge.

We can find out whether u is the ancestor of  v or v is the ancestor of u, by using start,finish times of u and v( if u.s<v.s<v.f<u.f then u is the ancestor of v,  or else if  v.s<u.s<u.s<u.f then v is the ancestor of u, where .s  is start time and .f is finish time of any vertex during DFS traversal).

Now if u is the ancestor of v, then we can use the method you mentioned(Just start from node v and then get its parent say y,now go to to node y in P and get its parent .Do this until we get the node u,and keep on printing all the nodes we access.)

If v is ancestor of u then the same process we can use but this time start with u(Just start from node u and then get its parent say y,now go to to node y in P and get its parent .Do this until we get the node v,and keep on printing all the nodes we access.)

---

@Sourav Basu,The entire story boils down to the fact that nodes with common parents will eventually form a cycle. How about self loops?Shouldn't this too be taken into account as well.

Answer 4

Here is what I think:

f(v){
    if(P[v] == u){  // Since cycle is gonna form everytime acc. to Q, so didn't define any base case for P[v] != u
        cout<<u;
    }
    else{
        f(P[v]);
        cout<<v;    // Print the path u -> v top down.
    }
}

Running Time = O(cycle length)

Is this correct?

Answer 5

In the below link i have explained the answer from basic. Just watch it you’ll not regret it definitely.

I have started solving #gateoverflow algorithm question here is #Algorithm question 1 answer.

#gate2021

https://youtu.be/wsnFk7wEj38

Answer 6

The answers here are not considering that we only have a parent array for our DFS tree. We cannot perform a dfs lookup from u and reach node v that easily. We would have to build a graph from the dfs tree. Which is not optimal.

We can just find the Least common Ancestor of u and v, following the parent pointers.
The edges involved will also be the starting elements of the LCA arrays.