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 <shashiski...@gmail.com> 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 <m...@shashwat.me> wrote:
>
>>
>>
>>
>> On Tue, Apr 29, 2014 at 4:56 PM, shashi kant <shashiski...@gmail.com>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 algogeeks+unsubscr...@googlegroups.com.
>>>
>>
>> --
>> 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 algogeeks+unsubscr...@googlegroups.com.
>>
>
> --
> 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 algogeeks+unsubscr...@googlegroups.com.
>
--
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 algogeeks+unsubscr...@googlegroups.com.
