This is the
linkhttp://apps.topcoder.com/forums/?module=ThreadthreadID=764182start=0mc=4#1614862to
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:-
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
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 srbh.ku...@gmail.com wrote:
You'd need: max(#vertices-with-0in-degree, #vertices-with-0out-degree)
edges at least.
On 8 October 2012 20:20, bharat b bagana.bharatku...@gmail.com wrote:
We are attempting for DAGs only.
Your graph is not acyclic. :)
On 9 October 2012 21:57, Jaspreet Singh jassajjassaj...@gmail.com 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 srbh.ku...@gmail.com wrote:
You'd need:
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 srbh.ku...@gmail.com wrote:
We are attempting
@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
count the no. of nodes having 0 in-degree.
On Mon, Oct 8, 2012 at 12:44 AM, atul anand atul.87fri...@gmail.com 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 bagana.bharatku...@gmail.com 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.comwrote:
count the no. of nodes having 0 in-degree.
On Mon, Oct 8, 2012 at 12:44 AM, atul anand
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 bagana.bharatku...@gmail.comwrote:
@jaspreet: take an ex:
B-A
B-C
B-D
Here the no.of zero-indegree is one . But its not the correct
You'd need: max(#vertices-with-0in-degree, #vertices-with-0out-degree)
edges at least.
On 8 October 2012 20:20, bharat b bagana.bharatku...@gmail.com 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
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_countin_count ie.
@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 atul.87fri...@gmail.com wrote:
find no. of cut vertex in the DAGthat will be the ans.
On 6 Oct 2012 19:33, KK kunalkapadi...@gmail.com wrote:
Given a
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 bagana.bharatku...@gmail.com 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,
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
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
find no. of cut vertex in the DAGthat will be the ans.
On 6 Oct 2012 19:33, KK kunalkapadi...@gmail.com 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
16 matches
Mail list logo
