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