You are not logged in. Please login at www.codechef.com to post your questions!

×

How to create adjacency list for this problem.

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

arpit728's gravatar image

1★arpit728
6831562
accept rate: 10%


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

vector<int> 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].

link

answered 27 Jan '16, 00:47

ankg's gravatar image

3★ankg
2113
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) sarvagya39434★

@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★

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

link

answered 30 Jan '16, 13:46

shubham99's gravatar image

2★shubham99
2403932
accept rate: 5%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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