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.
