Re: [algogeeks] Min Edges to be added to DAG to make it Strongly connected?

[atul anand]

i have doubts in miscof answer ,
your question says that given graph is a DAG ,but in miscof's reply he is
considering directed graph which contain say n strongly connected component
, so if we consider dat there are n strongly connected component in your
graph then that graph is not a DAG(this will violates your question).
But if you are considering all nodes in a given strongly connected graph as
a single node then given graph will form DAG.
so there is lot of difference in the twoso please clarify your
question.

On Wed, Oct 10, 2012 at 1:26 AM, KK  wrote:

> This is the 
> linkto
>  the answer given by misof.. and it worked!!
>
>
> On Sunday, 7 October 2012 00:41:48 UTC+5:30, kailash wrote:
>
>> @atul: No,it's not the correct answer. Let's take an example of star like
>> DAG:-
>>
>> A
>> -->B-->C
>>
>>   |
>>
>>   V
>>
>>  D
>> This DAG contains only one cut vertex(B) but we need to add two edges to
>> make it strongly connected.
>>
>>
>>
>>
>> On Sat, Oct 6, 2012 at 7:37 PM, atul anand  wrote:
>>
>>> find no. of cut vertex in the DAGthat will be the ans.
>>> On 6 Oct 2012 19:33, "KK"  wrote:
>>>
 Given a DAG(Directed Acyclic Graph). How to find out the minimum number
 of edges that needs to be added so that the given graph becomes Strongly
 Connected?

 --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To view this discussion on the web visit https://groups.google.com/d/**
 msg/algogeeks/-/PbR3j9S5OXUJ
 .
 To post to this group, send email to algo...@googlegroups.com.
 To unsubscribe from this group, send email to algogeeks+...@**
 googlegroups.com.

 For more options, visit this group at http://groups.google.com/**
 group/algogeeks?hl=en .

>>>  --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algo...@googlegroups.com.
>>> To unsubscribe from this group, send email to algogeeks+...@**
>>> googlegroups.com.
>>>
>>> For more options, visit this group at http://groups.google.com/**
>>> group/algogeeks?hl=en .
>>>
>>
>>
>>
>> --
>>
>> --
>>
>> ‘Kailash Bagaria’
>> B-tech 4th year
>> Computer Science & Engineering
>> Indian Institute of Technology, Roorkee
>> Roorkee, India (247667)
>>
>>   --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/O5kS0uhrsr4J.
>
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Min Edges to be added to DAG to make it Strongly connected?

[KK]

This is the 
linkto
 the answer given by misof.. and it worked!!

On Sunday, 7 October 2012 00:41:48 UTC+5:30, kailash wrote:
>
> @atul: No,it's not the correct answer. Let's take an example of star like 
> DAG:-
>
> A
> -->B-->C
>   
>   |
>   
>   V
>   
>  D
> This DAG contains only one cut vertex(B) but we need to add two edges to 
> make it strongly connected.
>   
>  
>
>
> On Sat, Oct 6, 2012 at 7:37 PM, atul anand 
> > wrote:
>
>> find no. of cut vertex in the DAGthat will be the ans.
>> On 6 Oct 2012 19:33, "KK" > wrote:
>>
>>> Given a DAG(Directed Acyclic Graph). How to find out the minimum number 
>>> of edges that needs to be added so that the given graph becomes Strongly 
>>> Connected?
>>>
>>> -- 
>>> You received this message because you are subscribed to the Google 
>>> Groups "Algorithm Geeks" group.
>>> To view this discussion on the web visit 
>>> https://groups.google.com/d/msg/algogeeks/-/PbR3j9S5OXUJ.
>>> To post to this group, send email to algo...@googlegroups.com
>>> .
>>> To unsubscribe from this group, send email to 
>>> algogeeks+...@googlegroups.com .
>>> For more options, visit this group at 
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>  -- 
>> You received this message because you are subscribed to the Google Groups 
>> "Algorithm Geeks" group.
>> To post to this group, send email to algo...@googlegroups.com
>> .
>> To unsubscribe from this group, send email to 
>> algogeeks+...@googlegroups.com .
>> For more options, visit this group at 
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> -- 
>
> --
>
> ‘Kailash Bagaria’
> B-tech 4th year
> Computer Science & Engineering
> Indian Institute of Technology, Roorkee
> Roorkee, India (247667)
>
> 

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/O5kS0uhrsr4J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Min Edges to be added to DAG to make it Strongly connected?

[Jaspreet Singh]

oh ok .. but then i think this ques should have a adv version for cyclic
too bcoz anyhow u have to make it at last a cyclic to make it fully
connected then why not the input should be like that.

Thanks

On Tue, Oct 9, 2012 at 10:13 PM, Saurabh Kumar  wrote:

> We are attempting for DAGs only.
> Your graph is not acyclic.  :)
>
>
> On 9 October 2012 21:57, Jaspreet Singh  wrote:
>
>> What if this :-
>> a-»b
>> ^--' c
>>
>> here max of both is 1 but ans is 2.
>> On Oct 8, 2012 11:38 PM, "Saurabh Kumar"  wrote:
>>
>>> You'd need:  max(#vertices-with-0in-degree, #vertices-with-0out-degree)
>>> edges at least.
>>>
>>> On 8 October 2012 20:20, bharat b  wrote:
>>>
 @jaspreet: take an ex:
  B->A
 B->C
 B->D
 Here the no.of zero-indegree is one . But its not the correct ans.


 On Mon, Oct 8, 2012 at 1:19 AM, Jaspreet Singh <
 jassajjassaj...@gmail.com> wrote:

> count the no. of nodes having 0 in-degree.
>
>
> On Mon, Oct 8, 2012 at 12:44 AM, atul anand 
> wrote:
>
>> yeah i read it wrongly .. i thought ques was asking to find total
>> strongly connected component in the graph
>>
>> On 10/7/12, bharat b  wrote:
>> > @atul : if there is no cut vertex, that doesn't mean that graph is
>> strongly
>> > connected ...
>> >
>> >
>> > On Sat, Oct 6, 2012 at 7:37 PM, atul anand 
>> wrote:
>> >
>> >> find no. of cut vertex in the DAGthat will be the ans.
>> >> On 6 Oct 2012 19:33, "KK"  wrote:
>> >>
>> >>> Given a DAG(Directed Acyclic Graph). How to find out the minimum
>> number
>> >>> of edges that needs to be added so that the given graph becomes
>> Strongly
>> >>> Connected?
>> >>>
>> >>> --
>> >>> You received this message because you are subscribed to the Google
>> >>> Groups
>> >>> "Algorithm Geeks" group.
>> >>> To view this discussion on the web visit
>> >>> https://groups.google.com/d/msg/algogeeks/-/PbR3j9S5OXUJ.
>> >>> To post to this group, send email to algogeeks@googlegroups.com.
>> >>> To unsubscribe from this group, send email to
>> >>> algogeeks+unsubscr...@googlegroups.com.
>> >>> For more options, visit this group at
>> >>> http://groups.google.com/group/algogeeks?hl=en.
>> >>>
>> >>  --
>> >> You received this message because you are subscribed to the Google
>> Groups
>> >> "Algorithm Geeks" group.
>> >> To post to this group, send email to algogeeks@googlegroups.com.
>> >> To unsubscribe from this group, send email to
>> >> algogeeks+unsubscr...@googlegroups.com.
>> >> For more options, visit this group at
>> >> http://groups.google.com/group/algogeeks?hl=en.
>> >>
>> >
>> > --
>> > You received this message because you are subscribed to the Google
>> Groups
>> > "Algorithm Geeks" group.
>> > To post to this group, send email to algogeeks@googlegroups.com.
>> > To unsubscribe from this group, send email to
>> > algogeeks+unsubscr...@googlegroups.com.
>> > For more options, visit this group at
>> > http://groups.google.com/group/algogeeks?hl=en.
>> >
>> >
>>
>> --
>> You received this message because you are subscribed to the Google
>> Groups "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>  --
> You received this message because you are subscribed to the Google
> Groups "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

  --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

>>>
>>>  --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this gr

Re: [algogeeks] Min Edges to be added to DAG to make it Strongly connected?

[Saurabh Kumar]

We are attempting for DAGs only.
Your graph is not acyclic.  :)

On 9 October 2012 21:57, Jaspreet Singh  wrote:

> What if this :-
> a-»b
> ^--' c
>
> here max of both is 1 but ans is 2.
> On Oct 8, 2012 11:38 PM, "Saurabh Kumar"  wrote:
>
>> You'd need:  max(#vertices-with-0in-degree, #vertices-with-0out-degree)
>> edges at least.
>>
>> On 8 October 2012 20:20, bharat b  wrote:
>>
>>> @jaspreet: take an ex:
>>>  B->A
>>> B->C
>>> B->D
>>> Here the no.of zero-indegree is one . But its not the correct ans.
>>>
>>>
>>> On Mon, Oct 8, 2012 at 1:19 AM, Jaspreet Singh <
>>> jassajjassaj...@gmail.com> wrote:
>>>
 count the no. of nodes having 0 in-degree.


 On Mon, Oct 8, 2012 at 12:44 AM, atul anand wrote:

> yeah i read it wrongly .. i thought ques was asking to find total
> strongly connected component in the graph
>
> On 10/7/12, bharat b  wrote:
> > @atul : if there is no cut vertex, that doesn't mean that graph is
> strongly
> > connected ...
> >
> >
> > On Sat, Oct 6, 2012 at 7:37 PM, atul anand 
> wrote:
> >
> >> find no. of cut vertex in the DAGthat will be the ans.
> >> On 6 Oct 2012 19:33, "KK"  wrote:
> >>
> >>> Given a DAG(Directed Acyclic Graph). How to find out the minimum
> number
> >>> of edges that needs to be added so that the given graph becomes
> Strongly
> >>> Connected?
> >>>
> >>> --
> >>> You received this message because you are subscribed to the Google
> >>> Groups
> >>> "Algorithm Geeks" group.
> >>> To view this discussion on the web visit
> >>> https://groups.google.com/d/msg/algogeeks/-/PbR3j9S5OXUJ.
> >>> To post to this group, send email to algogeeks@googlegroups.com.
> >>> To unsubscribe from this group, send email to
> >>> algogeeks+unsubscr...@googlegroups.com.
> >>> For more options, visit this group at
> >>> http://groups.google.com/group/algogeeks?hl=en.
> >>>
> >>  --
> >> You received this message because you are subscribed to the Google
> Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com.
> >> For more options, visit this group at
> >> http://groups.google.com/group/algogeeks?hl=en.
> >>
> >
> > --
> > You received this message because you are subscribed to the Google
> Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> > http://groups.google.com/group/algogeeks?hl=en.
> >
> >
>
> --
> You received this message because you are subscribed to the Google
> Groups "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
  --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

>>>
>>>  --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups

Re: [algogeeks] Min Edges to be added to DAG to make it Strongly connected?

[Jaspreet Singh]

What if this :-
a-»b
^--' c

here max of both is 1 but ans is 2.
On Oct 8, 2012 11:38 PM, "Saurabh Kumar"  wrote:

> You'd need:  max(#vertices-with-0in-degree, #vertices-with-0out-degree)
> edges at least.
>
> On 8 October 2012 20:20, bharat b  wrote:
>
>> @jaspreet: take an ex:
>>  B->A
>> B->C
>> B->D
>> Here the no.of zero-indegree is one . But its not the correct ans.
>>
>>
>> On Mon, Oct 8, 2012 at 1:19 AM, Jaspreet Singh > > wrote:
>>
>>> count the no. of nodes having 0 in-degree.
>>>
>>>
>>> On Mon, Oct 8, 2012 at 12:44 AM, atul anand wrote:
>>>
 yeah i read it wrongly .. i thought ques was asking to find total
 strongly connected component in the graph

 On 10/7/12, bharat b  wrote:
 > @atul : if there is no cut vertex, that doesn't mean that graph is
 strongly
 > connected ...
 >
 >
 > On Sat, Oct 6, 2012 at 7:37 PM, atul anand 
 wrote:
 >
 >> find no. of cut vertex in the DAGthat will be the ans.
 >> On 6 Oct 2012 19:33, "KK"  wrote:
 >>
 >>> Given a DAG(Directed Acyclic Graph). How to find out the minimum
 number
 >>> of edges that needs to be added so that the given graph becomes
 Strongly
 >>> Connected?
 >>>
 >>> --
 >>> You received this message because you are subscribed to the Google
 >>> Groups
 >>> "Algorithm Geeks" group.
 >>> To view this discussion on the web visit
 >>> https://groups.google.com/d/msg/algogeeks/-/PbR3j9S5OXUJ.
 >>> To post to this group, send email to algogeeks@googlegroups.com.
 >>> To unsubscribe from this group, send email to
 >>> algogeeks+unsubscr...@googlegroups.com.
 >>> For more options, visit this group at
 >>> http://groups.google.com/group/algogeeks?hl=en.
 >>>
 >>  --
 >> You received this message because you are subscribed to the Google
 Groups
 >> "Algorithm Geeks" group.
 >> To post to this group, send email to algogeeks@googlegroups.com.
 >> To unsubscribe from this group, send email to
 >> algogeeks+unsubscr...@googlegroups.com.
 >> For more options, visit this group at
 >> http://groups.google.com/group/algogeeks?hl=en.
 >>
 >
 > --
 > You received this message because you are subscribed to the Google
 Groups
 > "Algorithm Geeks" group.
 > To post to this group, send email to algogeeks@googlegroups.com.
 > To unsubscribe from this group, send email to
 > algogeeks+unsubscr...@googlegroups.com.
 > For more options, visit this group at
 > http://groups.google.com/group/algogeeks?hl=en.
 >
 >

 --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


>>>  --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Min Edges to be added to DAG to make it Strongly connected?

[Saurabh Kumar]

You'd need:  max(#vertices-with-0in-degree, #vertices-with-0out-degree)
edges at least.

On 8 October 2012 20:20, bharat b  wrote:

> @jaspreet: take an ex:
>  B->A
> B->C
> B->D
> Here the no.of zero-indegree is one . But its not the correct ans.
>
>
> On Mon, Oct 8, 2012 at 1:19 AM, Jaspreet Singh 
> wrote:
>
>> count the no. of nodes having 0 in-degree.
>>
>>
>> On Mon, Oct 8, 2012 at 12:44 AM, atul anand wrote:
>>
>>> yeah i read it wrongly .. i thought ques was asking to find total
>>> strongly connected component in the graph
>>>
>>> On 10/7/12, bharat b  wrote:
>>> > @atul : if there is no cut vertex, that doesn't mean that graph is
>>> strongly
>>> > connected ...
>>> >
>>> >
>>> > On Sat, Oct 6, 2012 at 7:37 PM, atul anand 
>>> wrote:
>>> >
>>> >> find no. of cut vertex in the DAGthat will be the ans.
>>> >> On 6 Oct 2012 19:33, "KK"  wrote:
>>> >>
>>> >>> Given a DAG(Directed Acyclic Graph). How to find out the minimum
>>> number
>>> >>> of edges that needs to be added so that the given graph becomes
>>> Strongly
>>> >>> Connected?
>>> >>>
>>> >>> --
>>> >>> You received this message because you are subscribed to the Google
>>> >>> Groups
>>> >>> "Algorithm Geeks" group.
>>> >>> To view this discussion on the web visit
>>> >>> https://groups.google.com/d/msg/algogeeks/-/PbR3j9S5OXUJ.
>>> >>> To post to this group, send email to algogeeks@googlegroups.com.
>>> >>> To unsubscribe from this group, send email to
>>> >>> algogeeks+unsubscr...@googlegroups.com.
>>> >>> For more options, visit this group at
>>> >>> http://groups.google.com/group/algogeeks?hl=en.
>>> >>>
>>> >>  --
>>> >> You received this message because you are subscribed to the Google
>>> Groups
>>> >> "Algorithm Geeks" group.
>>> >> To post to this group, send email to algogeeks@googlegroups.com.
>>> >> To unsubscribe from this group, send email to
>>> >> algogeeks+unsubscr...@googlegroups.com.
>>> >> For more options, visit this group at
>>> >> http://groups.google.com/group/algogeeks?hl=en.
>>> >>
>>> >
>>> > --
>>> > You received this message because you are subscribed to the Google
>>> Groups
>>> > "Algorithm Geeks" group.
>>> > To post to this group, send email to algogeeks@googlegroups.com.
>>> > To unsubscribe from this group, send email to
>>> > algogeeks+unsubscr...@googlegroups.com.
>>> > For more options, visit this group at
>>> > http://groups.google.com/group/algogeeks?hl=en.
>>> >
>>> >
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Min Edges to be added to DAG to make it Strongly connected?

[Jaspreet Singh]

ok the algo will go like this :
count no of nodes having only indegree 0 , only outdegree 0 and both 0. say
in_count,out_count and both_count are the corresponding counts.
now decrease the counts accordingly if u found a matching like u can
decrease in_count by both_count if both_count0 and in
degree>0 your graph is connected !! and i m just making that.

On Mon, Oct 8, 2012 at 8:37 PM, Jaspreet Singh wrote:

> yeah you are correct bharat .. so i think it should be no. of nodes
> having 0 (in-degree + out-degree). what say ?
>
>
> On Mon, Oct 8, 2012 at 8:20 PM, bharat b wrote:
>
>> @jaspreet: take an ex:
>>  B->A
>> B->C
>> B->D
>> Here the no.of zero-indegree is one . But its not the correct ans.
>>
>>
>> On Mon, Oct 8, 2012 at 1:19 AM, Jaspreet Singh > > wrote:
>>
>>> count the no. of nodes having 0 in-degree.
>>>
>>>
>>> On Mon, Oct 8, 2012 at 12:44 AM, atul anand wrote:
>>>
 yeah i read it wrongly .. i thought ques was asking to find total
 strongly connected component in the graph

 On 10/7/12, bharat b  wrote:
 > @atul : if there is no cut vertex, that doesn't mean that graph is
 strongly
 > connected ...
 >
 >
 > On Sat, Oct 6, 2012 at 7:37 PM, atul anand 
 wrote:
 >
 >> find no. of cut vertex in the DAGthat will be the ans.
 >> On 6 Oct 2012 19:33, "KK"  wrote:
 >>
 >>> Given a DAG(Directed Acyclic Graph). How to find out the minimum
 number
 >>> of edges that needs to be added so that the given graph becomes
 Strongly
 >>> Connected?
 >>>
 >>> --
 >>> You received this message because you are subscribed to the Google
 >>> Groups
 >>> "Algorithm Geeks" group.
 >>> To view this discussion on the web visit
 >>> https://groups.google.com/d/msg/algogeeks/-/PbR3j9S5OXUJ.
 >>> To post to this group, send email to algogeeks@googlegroups.com.
 >>> To unsubscribe from this group, send email to
 >>> algogeeks+unsubscr...@googlegroups.com.
 >>> For more options, visit this group at
 >>> http://groups.google.com/group/algogeeks?hl=en.
 >>>
 >>  --
 >> You received this message because you are subscribed to the Google
 Groups
 >> "Algorithm Geeks" group.
 >> To post to this group, send email to algogeeks@googlegroups.com.
 >> To unsubscribe from this group, send email to
 >> algogeeks+unsubscr...@googlegroups.com.
 >> For more options, visit this group at
 >> http://groups.google.com/group/algogeeks?hl=en.
 >>
 >
 > --
 > You received this message because you are subscribed to the Google
 Groups
 > "Algorithm Geeks" group.
 > To post to this group, send email to algogeeks@googlegroups.com.
 > To unsubscribe from this group, send email to
 > algogeeks+unsubscr...@googlegroups.com.
 > For more options, visit this group at
 > http://groups.google.com/group/algogeeks?hl=en.
 >
 >

 --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


>>>  --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Min Edges to be added to DAG to make it Strongly connected?

[Jaspreet Singh]

yeah you are correct bharat .. so i think it should be no. of nodes having
0 (in-degree + out-degree). what say ?

On Mon, Oct 8, 2012 at 8:20 PM, bharat b wrote:

> @jaspreet: take an ex:
>  B->A
> B->C
> B->D
> Here the no.of zero-indegree is one . But its not the correct ans.
>
>
> On Mon, Oct 8, 2012 at 1:19 AM, Jaspreet Singh 
> wrote:
>
>> count the no. of nodes having 0 in-degree.
>>
>>
>> On Mon, Oct 8, 2012 at 12:44 AM, atul anand wrote:
>>
>>> yeah i read it wrongly .. i thought ques was asking to find total
>>> strongly connected component in the graph
>>>
>>> On 10/7/12, bharat b  wrote:
>>> > @atul : if there is no cut vertex, that doesn't mean that graph is
>>> strongly
>>> > connected ...
>>> >
>>> >
>>> > On Sat, Oct 6, 2012 at 7:37 PM, atul anand 
>>> wrote:
>>> >
>>> >> find no. of cut vertex in the DAGthat will be the ans.
>>> >> On 6 Oct 2012 19:33, "KK"  wrote:
>>> >>
>>> >>> Given a DAG(Directed Acyclic Graph). How to find out the minimum
>>> number
>>> >>> of edges that needs to be added so that the given graph becomes
>>> Strongly
>>> >>> Connected?
>>> >>>
>>> >>> --
>>> >>> You received this message because you are subscribed to the Google
>>> >>> Groups
>>> >>> "Algorithm Geeks" group.
>>> >>> To view this discussion on the web visit
>>> >>> https://groups.google.com/d/msg/algogeeks/-/PbR3j9S5OXUJ.
>>> >>> To post to this group, send email to algogeeks@googlegroups.com.
>>> >>> To unsubscribe from this group, send email to
>>> >>> algogeeks+unsubscr...@googlegroups.com.
>>> >>> For more options, visit this group at
>>> >>> http://groups.google.com/group/algogeeks?hl=en.
>>> >>>
>>> >>  --
>>> >> You received this message because you are subscribed to the Google
>>> Groups
>>> >> "Algorithm Geeks" group.
>>> >> To post to this group, send email to algogeeks@googlegroups.com.
>>> >> To unsubscribe from this group, send email to
>>> >> algogeeks+unsubscr...@googlegroups.com.
>>> >> For more options, visit this group at
>>> >> http://groups.google.com/group/algogeeks?hl=en.
>>> >>
>>> >
>>> > --
>>> > You received this message because you are subscribed to the Google
>>> Groups
>>> > "Algorithm Geeks" group.
>>> > To post to this group, send email to algogeeks@googlegroups.com.
>>> > To unsubscribe from this group, send email to
>>> > algogeeks+unsubscr...@googlegroups.com.
>>> > For more options, visit this group at
>>> > http://groups.google.com/group/algogeeks?hl=en.
>>> >
>>> >
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Min Edges to be added to DAG to make it Strongly connected?

[bharat b]

@jaspreet: take an ex:
 B->A
B->C
B->D
Here the no.of zero-indegree is one . But its not the correct ans.

On Mon, Oct 8, 2012 at 1:19 AM, Jaspreet Singh wrote:

> count the no. of nodes having 0 in-degree.
>
>
> On Mon, Oct 8, 2012 at 12:44 AM, atul anand wrote:
>
>> yeah i read it wrongly .. i thought ques was asking to find total
>> strongly connected component in the graph
>>
>> On 10/7/12, bharat b  wrote:
>> > @atul : if there is no cut vertex, that doesn't mean that graph is
>> strongly
>> > connected ...
>> >
>> >
>> > On Sat, Oct 6, 2012 at 7:37 PM, atul anand 
>> wrote:
>> >
>> >> find no. of cut vertex in the DAGthat will be the ans.
>> >> On 6 Oct 2012 19:33, "KK"  wrote:
>> >>
>> >>> Given a DAG(Directed Acyclic Graph). How to find out the minimum
>> number
>> >>> of edges that needs to be added so that the given graph becomes
>> Strongly
>> >>> Connected?
>> >>>
>> >>> --
>> >>> You received this message because you are subscribed to the Google
>> >>> Groups
>> >>> "Algorithm Geeks" group.
>> >>> To view this discussion on the web visit
>> >>> https://groups.google.com/d/msg/algogeeks/-/PbR3j9S5OXUJ.
>> >>> To post to this group, send email to algogeeks@googlegroups.com.
>> >>> To unsubscribe from this group, send email to
>> >>> algogeeks+unsubscr...@googlegroups.com.
>> >>> For more options, visit this group at
>> >>> http://groups.google.com/group/algogeeks?hl=en.
>> >>>
>> >>  --
>> >> You received this message because you are subscribed to the Google
>> Groups
>> >> "Algorithm Geeks" group.
>> >> To post to this group, send email to algogeeks@googlegroups.com.
>> >> To unsubscribe from this group, send email to
>> >> algogeeks+unsubscr...@googlegroups.com.
>> >> For more options, visit this group at
>> >> http://groups.google.com/group/algogeeks?hl=en.
>> >>
>> >
>> > --
>> > You received this message because you are subscribed to the Google
>> Groups
>> > "Algorithm Geeks" group.
>> > To post to this group, send email to algogeeks@googlegroups.com.
>> > To unsubscribe from this group, send email to
>> > algogeeks+unsubscr...@googlegroups.com.
>> > For more options, visit this group at
>> > http://groups.google.com/group/algogeeks?hl=en.
>> >
>> >
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Min Edges to be added to DAG to make it Strongly connected?

[Jaspreet Singh]

count the no. of nodes having 0 in-degree.

On Mon, Oct 8, 2012 at 12:44 AM, atul anand  wrote:

> yeah i read it wrongly .. i thought ques was asking to find total
> strongly connected component in the graph
>
> On 10/7/12, bharat b  wrote:
> > @atul : if there is no cut vertex, that doesn't mean that graph is
> strongly
> > connected ...
> >
> >
> > On Sat, Oct 6, 2012 at 7:37 PM, atul anand 
> wrote:
> >
> >> find no. of cut vertex in the DAGthat will be the ans.
> >> On 6 Oct 2012 19:33, "KK"  wrote:
> >>
> >>> Given a DAG(Directed Acyclic Graph). How to find out the minimum number
> >>> of edges that needs to be added so that the given graph becomes
> Strongly
> >>> Connected?
> >>>
> >>> --
> >>> You received this message because you are subscribed to the Google
> >>> Groups
> >>> "Algorithm Geeks" group.
> >>> To view this discussion on the web visit
> >>> https://groups.google.com/d/msg/algogeeks/-/PbR3j9S5OXUJ.
> >>> To post to this group, send email to algogeeks@googlegroups.com.
> >>> To unsubscribe from this group, send email to
> >>> algogeeks+unsubscr...@googlegroups.com.
> >>> For more options, visit this group at
> >>> http://groups.google.com/group/algogeeks?hl=en.
> >>>
> >>  --
> >> You received this message because you are subscribed to the Google
> Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com.
> >> For more options, visit this group at
> >> http://groups.google.com/group/algogeeks?hl=en.
> >>
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> > http://groups.google.com/group/algogeeks?hl=en.
> >
> >
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Min Edges to be added to DAG to make it Strongly connected?

[Kailash Bagaria]

@atul: No,it's not the correct answer. Let's take an example of star like
DAG:-

A-->
B-->C

|

V

   D
This DAG contains only one cut vertex(B) but we need to add two edges to
make it strongly connected.




On Sat, Oct 6, 2012 at 7:37 PM, atul anand  wrote:

> find no. of cut vertex in the DAGthat will be the ans.
> On 6 Oct 2012 19:33, "KK"  wrote:
>
>> Given a DAG(Directed Acyclic Graph). How to find out the minimum number
>> of edges that needs to be added so that the given graph becomes Strongly
>> Connected?
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/PbR3j9S5OXUJ.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 

--

‘Kailash Bagaria’
B-tech 4th year
Computer Science & Engineering
Indian Institute of Technology, Roorkee
Roorkee, India (247667)

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Min Edges to be added to DAG to make it Strongly connected?

[atul anand]

yeah i read it wrongly .. i thought ques was asking to find total
strongly connected component in the graph

On 10/7/12, bharat b  wrote:
> @atul : if there is no cut vertex, that doesn't mean that graph is strongly
> connected ...
>
>
> On Sat, Oct 6, 2012 at 7:37 PM, atul anand  wrote:
>
>> find no. of cut vertex in the DAGthat will be the ans.
>> On 6 Oct 2012 19:33, "KK"  wrote:
>>
>>> Given a DAG(Directed Acyclic Graph). How to find out the minimum number
>>> of edges that needs to be added so that the given graph becomes Strongly
>>> Connected?
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups
>>> "Algorithm Geeks" group.
>>> To view this discussion on the web visit
>>> https://groups.google.com/d/msg/algogeeks/-/PbR3j9S5OXUJ.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Min Edges to be added to DAG to make it Strongly connected?

[bharat b]

@atul : if there is no cut vertex, that doesn't mean that graph is strongly
connected ...


On Sat, Oct 6, 2012 at 7:37 PM, atul anand  wrote:

> find no. of cut vertex in the DAGthat will be the ans.
> On 6 Oct 2012 19:33, "KK"  wrote:
>
>> Given a DAG(Directed Acyclic Graph). How to find out the minimum number
>> of edges that needs to be added so that the given graph becomes Strongly
>> Connected?
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/PbR3j9S5OXUJ.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Min Edges to be added to DAG to make it Strongly connected?

[atul anand]

find no. of cut vertex in the DAGthat will be the ans.
On 6 Oct 2012 19:33, "KK"  wrote:

> Given a DAG(Directed Acyclic Graph). How to find out the minimum number of
> edges that needs to be added so that the given graph becomes Strongly
> Connected?
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/PbR3j9S5OXUJ.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Min Edges to be added to DAG to make it Strongly connected?

[KK]

Given a DAG(Directed Acyclic Graph). How to find out the minimum number of 
edges that needs to be added so that the given graph becomes Strongly 
Connected?

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/T6idnKJ0It0J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Min Edges to be added to DAG to make it Strongly connected?

[KK]

Given a DAG(Directed Acyclic Graph). How to find out the minimum number of 
edges that needs to be added so that the given graph becomes Strongly 
Connected?

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/PbR3j9S5OXUJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.