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