How to solve this graph problem from CodeNation ?

Правка en2, от LovesProgramming, 2019-07-22 13:53:50

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 :-)

Теги #graph theory

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский LovesProgramming 2019-07-22 13:53:50 15 Tiny change: 'dges:- [1,n*(n-1)/2' -> 'dges:- [1,minimum(100000,n*(n-1)/2'
en1 Английский LovesProgramming 2019-07-22 13:48:57 872 Initial revision (published)