Sid, Your proposal is to try removing every possible combination of nodes and for each case, do a DFS to determine if the graph is still connected?
What is the time complexity of that approach? Don On Friday, May 9, 2014 4:58:15 AM UTC-4, siddharam wrote: > > 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]<javascript:> > > 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]<javascript:> >> > wrote: >> >>> >>> >>> >>> On Tue, Apr 29, 2014 at 4:56 PM, shashi kant >>> <[email protected]<javascript:> >>> > 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] <javascript:>. >>>> >>> >>> -- >>> 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] <javascript:>. >>> >> >> -- >> 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] <javascript:>. >> > > -- 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].
