Stuck in Graph Theory. Need help!

help
1

Hello everyone, I recently started the concept of Graph theory and covered breadth-first search, depth-first search, breadth-first traversal, and depth-first traversal in theory only, but I want to solve problems out there and don’t know where to get the proper editorials for those…like creating a graph using the user inputs and searching for the required nodes.

There is a problem where I’m stuck in and that is, given N numbers(1, 2, …N), the connections between the nodes are given as pairs and two special nodes are provided such as say 3 and 6(the special nodes are always directly connected)…we need to find all the nodes that are common to both the special nodes or somehow connected to both the special nodes.

For example, let’s consider a case where N = 10 and the special nodes are 4 and 5.
The connections between the nodes are given below,
1 4
10 4
5 8
7 6
2 3
8 9
4 5
3 1
2 5
3 7

We need to find the solution nodes that are common and print it as follows,
1 2 3 6 7
Someone help me with this.

3

Take a look at the implementation for BFS in my GitHub repository. It is well commented. I will be adding one for DFS soon.
Link: https://github.com/arujbansal/Data-Structures-and-Algorithms/tree/master/Graphs

Edit: Can you also provide the problem link?

2 Likes
4

Thank you so much brother…this really helped a lot.
Thanks again :relaxed: :grin:

5

I have also uploaded the implementation of DFS.

1 Like
6

I’m having a confusion here…will this work on multiple test cases as because the algorithm has a global vector array adjacency list i.e. vector<int> AdjList[N]; if we move further from one test case to another then the elements of the previous test cases are there and that might affect the output of the ongoing test…isn’t it @arujbansal1.
Can you have a look at that?

7

just use

for(int i=0;i<n;i++){
     adj[i].clear();
}
2 Likes
8

Yaa…that worked, actually I was trying to pop out the elements one by one…my bad :sweat_smile: :sweat_smile:…Thanks @everule1

9

If you wanna practice questions related to graph you can practice it on codemonk

1 Like
10

If you have multiple test cases and you want simplicity, just declare the Adjacency List inside your test case loop. You won’t have to call AdjList[I].clear(). You can pass this list into the function as an argument instead. You can do it any way you prefer.

1 Like
11

I did that earlier but it was showing runtime error…clearing the adjacency list at last worked.