CWAY - Counting paths in a complete graph
A complete graph of N verticles is a graph in which there is an edge between every pair of nodes.
Your task is to count the number of paths between any pair of nodes in the graph. Note that a path cannot visit a vertex more than once.
A single integer N that is the number of verticles in the graph (2 ≤ N ≤ 1000).
A single integer that is the number of paths between any two nodes in the graph.
Input 4 Output 5 Description For example, there are 5 paths between 1 and 2: 1-2 1-3-2 1-3-4-2 1-4-2 1-4-3-2
100 but we should use big integers. The answer for n = 1000 is extremely large.
Nice one...!! :)
I got 100 instead of 90 when I took into account N<2 (result 0 since there aren't any two distinct nodes).Last edit: 2009-08-04 19:50:09