How to create adjacency list for this problem.

bfs
dijkstra
dynamic-programming
editorial
graph
shortest-path

#1

I am solving this question using bfs as propsed in editorial, but I am not getting how the adjacency list will be generated for this graph.

Link to the Editorial


#2

The adjacency list that you will use will be as follows :

vector graph[n]; //This is basically an array of n cells, each cell having it’s data type as a vector.

You iterate a variable i from 1 to n. For every index i, you push_back Si+1, Si-1, and all those indexes j such that Si == Sj into graph*.

This way, you get the all possible adjacent nodes to a node i, in the vector graph*.


#3

@ankg has explained quite nicely but if you want to look at implementation for reference here’s the link


#4

If suppose I have 5 on the first index and also 5 on the 5th index then index 5 should be there in adjacency list of 1. Ho this situation will be taken care of.


#5

@arpit728 : I dont think you actually need to build the graph. Just store indexes of each digit . Refer this if you still don’t understand.


#6

@sarvagya3943

The solution link you mentioned, it is generating graph only?? right.


#7

@ankg

I got you n that for every index i push si-1 and si+1 into its adjacency list but to find si==sj I will have to iterate through all graph again and will increase the complexity.