use DFS
remove 1( and all combination of 2 to n-2 nodes) node aply DFS Thank you, Sid. phone:+91-8971070727, +91-9916809982 On Sun, May 4, 2014 at 10:14 PM, shashi kant <[email protected]> wrote: > > @shaswat : dude it's obvious that graph will be divided into more than 1 > components as mentioned in 3rd line. [mistakenly wrote only 2 but 3rd gives > all hints] > > and yes that question asked to get at max set of 3 elements size solution. > but i wanted to generalize that fact. > > @atul articulation point is a way to just get problem solved ... > step 1: find articulation points > step2 : if(at least 1 articulation point){ > add this vertex to RESULT_SET and return RESULT_SET > } > else if(no such articulation point){ > then remove any vertex ------do dfs to find if graph gets > disconnected > if(graph disconnected) { > add vertex to set RESULT_SET and return > RESULT_SET. > } > else { > add vertex to set RESULT_SET > remove this vertex from graph and repeat > step1->step2 > } > } > > Not an efficient way but i did solved it this way . ... > > what i'm looking for is a better way . > > > > > > > > > > > > *Shashi Kant * > *"Think positive and find fuel in failure"* > http://thinkndoawesome.blogspot.com/ > *Senior Software Engineer* > *Samsung Research India Bangalore .* > > > On Tue, Apr 29, 2014 at 10:57 PM, Shashwat Anand <[email protected]> wrote: > >> >> >> >> On Tue, Apr 29, 2014 at 4:56 PM, shashi kant <[email protected]>wrote: >> >>> Problem is as follows: >>> >> >> You have given a terrible description of problem. >> >> >>> >>> 1. Given a connected graph. >>> >> >> Connected, how ? Is the graph directed or undirected ? >> >> >>> 2. Remove a vertex out of it and if graph is divided into two components >>> return that vertex. >>> >> >> Are you sure about two component part ? >> What if graph is a star graph, you can take out the nucleus and it will >> be divided into N - 1 connected component. Will that not be ok ? Does it >> have to be *only* two components. >> >> >>> 3. else find a set of vertices to be removed that will divide graph into >>> more than 1 component. >>> >> >> Does that set has to be minimum ? If not why not simply remove N - 2 >> vertices and make is into two connected components. >> What if graph only have one node ? The question loses its meaning here. >> >> >>> >>> >>> >>> Please Help me out here .. probably min-cut problem >>> http://www.geeksforgeeks.org/minimum-cut-in-a-directed-graph/ is >>> suitable here. >>> >> >> Can you please explain, how is flow suitable here ? >> >> FWIW, I see this question as broken and unclear. >> >> >>> >>> *Thanks & Regards,* >>> *Shashi Kant * >>> *"Think positive and find fuel in failure"* >>> http://thinkndoawesome.blogspot.com/ >>> *Senior Software Engineer* >>> *Samsung Research India Bangalore .* >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to [email protected]. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
