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

Last Updated: 22 Jul, 2021

Easy

```
Vertices are numbered through 0 to V - 1.
```

```
The first line contains a single integer ‘T’ denoting the number of test cases. Then each testcase follow.
The first line of each test case contains two integers ‘V’ and ‘E’ denoting the number of vertices and edges in the graph.
The next ‘E’ lines of the test case contain two space-separated integers ‘a’ and ‘b’ denoting that there exists an edge between ‘a’ and ‘b’.
The last line of the test case contains two space-separated integers ‘v1’ and ‘v2’ denoting the starting vertex and ending vertex.
```

```
For each test case, print the path from ‘v1’ to ‘v2’ in reverse order.
Output for each test case will be printed in a separate line.
```

```
You are not required to print anything; it has already been taken care of. Just implement the function and return a list of paths.
If there is no path between the vertices return an empty list.If the path is valid then it will print true else it will print false.
```

```
1 <= T <= 10
1 <= V <= 1000
1 <= E <= (V * (V - 1)) / 2
0 <= v1, v2 <= V-1
Time Limit: 1sec
```

In this approach, iterate through the whole graph using BFS and whenever you encounter a new node, update the parent of the new node by the current node.

The steps are as follows :

- Initialize a list
**par**with -1 to store the parent of nodes. - Create a graph using the given nodes and a queue for storing the nodes to iterate through breadth-first search.
- Push
**v1**to the queue and start Breadth-first search till the queue is not empty. - Iterate through all the connected nodes from the current node.
- Update the parent of new nodes.
- Push the current element in the queue to iterate all the nodes connected to this node.
- After the completion of BFS, push the parent of the current node in a list
**answer**and go to the index of the par to find the parent of parent till we get -1. - If the final node in the
**answer**list is not**v1**return an empty list. - Return
**answer**.

Similar problems

Valid Arrangement of Pairs

Hard

Posted: 28 Jan, 2022

Valid Arrangement of Pairs

Hard

Posted: 28 Jan, 2022

Valid Arrangement of Pairs

Hard

Posted: 28 Jan, 2022

Valid Arrangement of Pairs

Hard

Posted: 28 Jan, 2022

Valid Arrangement of Pairs

Hard

Posted: 28 Jan, 2022

Left Right Print

Moderate

Posted: 9 Jul, 2022

COUNT ISLANDS

Moderate

Posted: 14 Sep, 2022

The Summit

Easy

Posted: 15 Sep, 2022

Distance to a Cycle in Undirected Graph

Moderate

Posted: 7 Nov, 2022