Counting in a DAG

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Counting in a DAG

Post by zobayer » Sat Mar 19, 2011 1:19 am

The problem is DAGCNT2 from SPOJ [ https://www.spoj.pl/problems/DAGCNT2 ]

Please anyone give me some hint about the proper algorithm to solve it. I used dfs with some optimization, but actually, I have gone upto n^2 somehow.

Thanks in advance!
You should not always say what you know, but you should always know what you say.

aab
New poster
Posts: 3
Joined: Wed Jun 22, 2011 11:47 am

Re: Counting in a DAG

Post by aab » Wed Jun 22, 2011 12:14 pm

Sort the vertices in topological order.You can do it in O(n+m) with dfs. Then for each vertex (starting from vertex of lower priority) calculate the sum of the weights of the vertices within its reach. This is also done in O(n+m). This should work.

Post Reply

Return to “Algorithms”