Given a directed connected non-weighted graph as input.I want to print a result to the output where result is the number of sub-graphs in which there is an edge between each pair of nodes of the sub-graph (in either of the directions) . The sub-graphs having zero nodes or a single node are also counted in the result.Since the result might be too large so result modulo 10^9 + 7 has to be printed.
The input-graph will not have multiple edges between any node pair and the edges are directed from node u to node v only if u < v .
Sample input:
3 // no of nodes
2 // no of edges
1 2
2 3
Sample output:
6
Reason:
1.no nodes
2.node 1
3.node 2
4.node 3
5.node 1,2
6.node 2,3
I am a using a recurrence result = sum(DP[nodes])+1, where DP[node] = sum(DP[adjacentnodes])+1 But this is giving 7 to the output . Kindly suggest some better method for this graph having number of nodes <= 3000 .
Thanks