ya it does because see here
http://en.wikipedia.org/wiki/Complete_graph
considering this
if u apply a dfs on this on k=10
dfs will travel all long 1,2,3,4,5
now when we apply bfs we will get it as
1
2 3 4 5
so all 2,3,4,5 will get eliminated since all are connected to the nodes
marked as yellow and if u select a node it will give u 1 then all gets
eliminated ie 2 ,3,4,5
thanks rahul for your question
On Mon, May 2, 2011 at 9:12 PM, Rahul Gulati <[email protected]>wrote:
> Try out some corner cases like complete graphs, etc. Does your algorithm
> return 1 for a complete graph?
>
> On Mon, May 2, 2011 at 9:09 PM, prajay shetty <[email protected]>wrote:
>
>> thanks for the admin coorporation please post the problem
>>
>>
>> On Mon, May 2, 2011 at 8:19 PM, prajay shetty
>> <[email protected]>wrote:
>>
>>>
>>> Hey all,
>>>
>>> Last week i was going trough corfment this is not a gcj problem but i
>>> had wrote an algorithm on np complete that is an independent set problem
>>> which has no cycle and no weight i had tried this algorithm on this type of
>>> graphs , can anyone provied me with counter example if any ,I taught this
>>> was the good one comunicate with you members since most of you will be good
>>> at DSA atleast more than me ): thanks for any help in the problem
>>>
>>> so here is our graph which has following properties as an example
>>> 1) node 1 is connected to node 2
>>> 2) node 2 is connected to node 3
>>> 3) node 3 is connected to node 1
>>> 4)node 2 is connected to node 5
>>> 5) node 2 is connected to node 4
>>> 6) node 5 is connectd to node 6
>>> 7)node 4 is connected to node 5
>>> 8) node 3 is connected to node 7
>>> 9) node 7 is connected to node 8
>>> 10) node 8 is connected to node 3
>>>
>>>
>>> First by seeing the graph we have independent set is 1,4,6,8
>>> Algorithm
>>>
>>> 1)We genearte dfs on graph g
>>> 2) We genearte bfs on g
>>> 3)DFS: here we modify our dfs a bit insteda as we go through dfs we
>>> color first node as blue and we dont color the next node and we color the
>>> next node blue this continues till we reach a dead end.,we list all the
>>> node that we marked as blue.
>>> for example we get the output as 1,3,5 now we explore 3 and we dont
>>> color 7 and then we color 8 like this we procceed, output is 1,3,4,6,8
>>> 4) BFS: we generate bfs, then once we got the list of nodes we maintain
>>> a pair node in an array as parent child in our array for example we store
>>> 1->2,3 and 2->4,5 and 3->7,8 for bfs we can just reduce the memory space by
>>> working on efficient ds on this.
>>> 5) then we color all the node as yellow in our bfs tree for the nodes
>>> that we obtain in step 3
>>> 6)now we check if the node that is in the list has a node connected to
>>> it colored as yellow ,if yes we delete it from our final list and in this
>>> way we get we remove 3 as 3 is connected to 1
>>> so we get our final list as 1,4,6,8
>>>
>>> just want to check if there is any counter example for this ...thanks for
>>> your help
>>>
>>>
>>> Note: step 3 can be done with step 1 and step 2 can be done with step 4
>>>
>>>
>>> --
>>> Regards ,Prajay
>>>
>>
>>
>>
>> --
>> Regards ,Prajay
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "google-codejam" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> For more options, visit this group at
>> http://groups.google.com/group/google-code?hl=en.
>>
>
>
>
> --
> Rahul Gulati
> [email protected]
> Department of Computer Science
> Jaypee Institute of Information Technology (Deemed University)
> India
>
> --
> You received this message because you are subscribed to the Google Groups
> "google-codejam" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/google-code?hl=en.
>
--
Regards ,Prajay
--
You received this message because you are subscribed to the Google Groups
"google-codejam" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en.
