LovesProgramming's blog

How to solve this graph problem from CodeNation ?
By LovesProgramming, history, 5 years ago, In English

This is a graph problem from the previous contest by Codenation .

Can you suggest some ideas to approach it or sketch the solution ?

Problem :- You are given a DAG(Directed A-cyclic Graph)

You are also given a source node- 'X' as input .

For each node 'Y' , find the number of paths that start at 'X' and end at 'Y' , such that the number of nodes visited along that path is even(including X an Y)

Note:- The path from X to X consists of only one node and hence the number of the nodes visited is odd. Hence there are 0 paths for X to X which consist of even number of nodes.

The number of test-cases:- 20

Number of nodes in the graph(n):- 100000.

Edges:- [1,minimum(100000,n*(n-1)/2]

Output:-'n' space separated integers such that the i'th element is the answer for node 'i', mod 1000000007

Thanks :-)

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Your text to link here... you can refer to above link here ... someone has already done a blog on that

→ Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

We can think of it as this way :

  1. We can reach a node by any of it's parents. Here, by parent, I mean any such node that has an outgoing edge to this node.

  2. So, the number of ways of reaching a node is the sum of the number of ways of reaching it's parents.

  3. Now, we know from observation 2 that we need to find out the number of ways of reaching all the parents of a node, to find out the number of ways to reach that node.

  4. From observation 3, we know that we need to process nodes in topological order. (think on it, if you didn't get it because this is the most important observation).

After this, it's simple implementation left

Implementation :

  1. Make topological sorting of nodes.

  2. Make a 2D DP — DP[N][2]. Here DP[i][0] stores the number of paths from node X to node i having even number of nodes and DP[i][1] stores the number of paths from node X to node i having odd number of nodes.

  3. One can easily see that DP[X][1] = 1, as there is one path having odd number of nodes from X to X. Keep all other values of DP table as 0.

  4. Now let suppose that topsort is a vector of nodes in topological order. And parent[i] is a vector of nodes containing parent of node i. You have this vector for each i such that 1 <= i <= n.

  5. If for a path, the number of nodes from X to a parent is even, then the number of nodes from X to that parent's child will be odd, and vice versa. This leads us to the following transition.

for(auto i : topsort){
  for(auto j : parent[i]){
    dp[i][0] = (dp[i][0] + dp[j][1]) % MOD;
    dp[i][1] = (dp[i][1] + dp[j][0]) % MOD;
  }
}

Now, the answer for each node i is in dp[i][0].

I hope it helps :)

If you have any doubts / need further clarifications, then feel free to ask.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    Can't we do it with simple dfs with an extra parameter "node count" which is incremented by 1 with each next dfs call and maintain an array which keeps count of number of even paths(i.e if "node count" is even we increase the value of vertex in the array by 1).It can be done in O(no. of edges) as here dfs would be done by traversing all the edges.Is there anything wrong in it..??

    Btw thank u for explaining the solution nicely.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      How would you account for multiple paths from source node $$$x$$$ to destination nodes $$$i$$$? If you allowed revisiting the nodes in the $$$DFS$$$ to account for the multiple paths, this would lead to an in-efficient solution. Topological ordering accounts for multiple paths to nodes in $$$DAG$$$s without revisiting nodes, by using the observation that no two nodes are reachable from one another. So, once answers of all nodes $$$p$$$ which have outgoing edges to node $$$i$$$ are computed, answer of node $$$i$$$ is ready to be computed.

      → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    smokescreen I think your dp transition states are not correct.It should be 

    dp[j][0] = (dp[i][1] + dp[j][0]) % MOD;
dp[j][1] = (dp[i][0] + dp[j][1]) % MOD;

    because dp[i][1] is giving odd number of nodes and edge i->j is adding so finally dp[j][0] should be there instead of dp[i][0] and same for the second case.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I was only able to 7 test case and got TLE in rest all. Was anyone able to pass all test cases ? If, What was the optimization ?

→ Reply