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 -- 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.
