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

Problem of the day

You are given a reference/address of a node in a connected undirected graph containing N nodes and M edges. You are supposed to return a clone of the given graph which is nothing but a deep copy. Each node in the graph contains an integer “data” and an array/list of its neighbours.

The structure of the graphNode class is as follows:

```
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.
```

Detailed explanation

```
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.
```

```
2
5
6
1 2
4 1
2 4
3 4
5 2
1 3
3
2
1 2
1 3
```

```
true
true
```

```
In the first test case, the returned graph contains 5 nodes and 6 edges which are:
1 2
4 1
2 4
3 4
5 2
1 3
Since it is similar to the given graph with different address nodes then the solution is correct.
In the second test case, the returned graph contains 3 nodes and 2 edges which are:
1 2
1 3
Since it is similar to the given graph with different address nodes then the solution is correct.
```

```
2
5
4
1 2
2 3
3 4
4 5
2
1
1 2
```

```
true
true
```

```
In the first test case, the returned graph contains 5 nodes and 4 edges which are:
1 2
2 3
3 4
4 5
Since it is similar to the given graph with different address nodes then the solution is correct.
In the second test case, the returned graph contains 2 nodes and 1 edge which is:
1 2
Since it is similar to the given graph with different address nodes then the solution is correct.
```