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