×

# How to create adjacency list for this problem.

 0 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 asked 23 Jan '16, 09:39 1★arpit728 683●15●62 accept rate: 10%

 1 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[i]. This way, you get the all possible adjacent nodes to a node i, in the vector graph[i]. answered 27 Jan '16, 00:47 3★ankg 211●3 accept rate: 33% 1 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. (29 Jan '16, 17:56) arpit7281★ @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. (30 Jan '16, 02:49) @sarvagya3943 The solution link you mentioned, it is generating graph only?? right. (30 Jan '16, 06:00) arpit7281★ @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. (30 Jan '16, 09:16) arpit7281★
 0 @ankg has explained quite nicely but if you want to look at implementation for reference here's the link answered 30 Jan '16, 13:46 240●3●9●32 accept rate: 5%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,477
×2,085
×1,197
×487
×164
×125

question asked: 23 Jan '16, 09:39

question was seen: 1,268 times

last updated: 30 Jan '16, 13:46