Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 25 Jan, 2021

Moderate

```
class graphNode
{
public:
int data;
vector<graphNode*> neighbours;
}
```

```
1. Nodes are numbered from 1 to N.
2. Your solution will run on multiple test cases. If you are using global variables make sure to clear them.
```

```
The first line of input contains an integer 'T' representing the number of the test case. Then the test cases are as follows.
The first line of each test case contains a single integer ‘N’ representing the number of nodes in the graph.
The second line of each test case contains a single integer ‘M’ representing the number of edges.
The next ‘M’ lines in each test case contain two integers ‘U’ and ‘V’ separated by a single space denoting an undirected edge between nodes U and V.
```

```
For each test case, print a single line containing "true" if the graph is cloned correctly otherwise it will print "false".
The output of each test case will be printed in a separate line.
```

```
You do not need to print anything; It has already been taken care of. Just implement the given function.
```

```
1 <= T <= 5
2 <= N <= 100000
1 <= M <= min(N(N-1)/2,100000)
1 <= E[i][0], E[i][1] <= N
Where ‘N’ is the number of nodes in the given graph, ‘M’ denotes the number of edges and ‘E’ denotes the edge matrix.
Time Limit: 1 sec.
```

To clone a graph, we will need to traverse it. The approach here is to use BFS graph traversal. To clone a graph, you need to have a copy of each node and you need to avoid copying the same node multiple times. So we need a mapping from an original node to its copy.

The steps are as follows :

- We need to keep track of the visited/cloned nodes to avoid making multiple copies of the same node. Hence, a HashMap is required in order to maintain all the nodes which have already been created. Where in the HashMap the key stores the address of the original node and the value stores the address of the cloned node.
- Now in order to reach each node and its neighbours, we are creating a queue for BFS traversal and a HashMap which keeps a track of all the nodes which are already created.
- Create a new node corresponding to the given reference node and insert that node in the HashMap which marks it as visited.
- Push the given reference node into a queue and now keep repeating the below steps until the queue isn’t empty.
- Get the front node and pop it from the queue and visit all its neighbours, now check if a new cloned node has already been created for each neighbouring node (check it in the HashMap).
- If it wasn’t created, then create a new clone node corresponding to the neighbour node and insert it into the HashMap and also push this node into the queue.
- Now add the cloned neighbours to “neighbours” list of the cloned node.
- Ultimately when the queue is empty, return the source node of the cloned graph.

To clone a graph, we will need to traverse it. The approach here is to use DFS graph traversal. To clone a graph, you need to have a copy of each node and you need to avoid copying the same node multiple times. So we need a mapping from an original node to its copy.

Steps are as follows:

- The algorithm starts at a given reference node in the given graph and explores as far as possible along each branch of the current node before backtracking.
- Now to keep the track of the visited/cloned nodes, a HashMap is required in order to maintain all the nodes which have already been created. Where in the HashMap the key stores the address of the original node and the value stores the address of the cloned node.
- The idea is to start from the starting node and mark the node and move to the adjacent unmarked node and continue this recursively until there is no unmarked adjacent node.
- Then backtrack and check for other unmarked nodes and traverse them.
- Create a recursive function that takes a node and the Hashmap which contains the copies of the nodes as arguments.
- Mark the current node as visited and create a new node for the cloned graph and insert the new node into the HashMap.
- Traverse all the adjacent nodes of the current node and for all unmarked nodes call the recursive function with the index of adjacent nodes.
- After visiting all neighbouring nodes, insert all the cloned neighbouring nodes into the neighbouring array/list of the current node.

Similar problems

Minimum Swaps To Make Identical Array

Moderate

Posted: 22 Jan, 2022

Find Center of Star Graph

Easy

Posted: 26 Jan, 2022

Critical Connections in a Network

Hard

Posted: 27 Jan, 2022

Critical Connections in a Network

Hard

Posted: 27 Jan, 2022

Critical Connections in a Network

Hard

Posted: 27 Jan, 2022

COUNT ISLANDS

Moderate

Posted: 14 Sep, 2022

Distance to a Cycle in Undirected Graph

Moderate

Posted: 7 Nov, 2022