Graph

Submit

Language is selected by the extension of the file. See the list of supported languages to know the extension of your language.

Problem

Given an undirected graph of n nodes, find the number of paths of length 'p' from first node to the remaining nodes.

Input:

First line contains two integers p(< n) and n where

p is the length of the path and n is the number of nodes in the graph

Further n lines contain the rows of adjacency matrix of the graph.

The adjacency matrix of a finite graph G on n vertices is the nxn matrix where the non-diagonal entry a[i][j] is the number of edges from vertex i to vertex j and the diagonal entry a[i][i] is 0.

Output:

For each input case, there is one output line consisting of n-1 values with i-th value denoting the number of paths of length p from first node to (i+1)th node.
<br><br>I've removed trailing whitespaces from 2nd output -- shinh<br><br>I've removed trailing whitespaces from 2nd input as well -- shinh

Options

exec is denied

now post-mortem time, all source codes will be revealed

Sample input:_

2 3
0 1 1
1 0 1
1 1 0
2 4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

Sample output:

1 1
2 2 2

Sample input:_

2 7
0 1 0 0 0 0 1
1 0 1 0 0 0 1
0 1 0 0 0 1 0
0 0 0 0 1 1 0
0 0 0 1 0 1 0
0 0 1 1 1 0 1
1 1 0 0 0 1 0
4 8
0 0 1 1 0 0 1 1
0 0 1 0 0 1 0 0
1 1 0 1 0 0 0 1
1 0 1 0 1 1 1 0
0 0 0 1 0 1 1 1
0 1 0 1 1 0 1 1
1 0 0 1 1 1 0 0
1 0 1 0 1 1 0 0
4 11
0 0 1 1 0 0 1 0 1 0 1
0 0 0 0 0 0 1 0 1 0 1
1 0 0 1 0 1 0 1 0 1 1
1 0 1 0 1 0 0 0 0 0 1
0 0 0 1 0 1 0 0 1 1 1
0 0 1 0 1 0 1 0 1 1 0
1 1 0 0 0 1 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0
1 1 0 0 1 1 0 0 0 0 0
0 0 1 0 1 1 0 0 0 0 1
1 1 1 1 1 0 0 0 0 1 0
1 2
0 0
0 0
1 2
0 0
0 0
1 4
0 1 0 0
1 0 1 1
0 1 0 0
0 1 0 0
2 4
0 1 0 0
1 0 1 1
0 1 0 0
0 1 0 0
3 8
0 0 1 1 0 0 1 1
0 0 0 1 0 0 0 0
1 0 0 0 0 1 0 0
1 1 0 0 1 1 0 1
0 0 0 1 0 0 0 1
0 0 1 1 0 0 0 1
1 0 0 0 0 0 0 1
1 0 0 1 1 1 1 0
3 6
0 1 1 1 1 1
1 0 0 1 1 1
1 0 0 0 1 1
1 1 0 0 1 1
1 1 1 1 0 0
1 1 1 1 0 0
1 9
0 1 1 1 1 1 0 1 0
1 0 1 0 1 1 0 1 0
1 1 0 1 1 0 1 0 1
1 0 1 0 0 1 1 0 1
1 1 1 0 0 0 1 0 1
1 1 0 1 0 0 1 1 1
0 0 1 1 1 1 0 1 1
1 1 0 0 0 1 1 0 1
0 0 1 1 1 1 1 1 0

Sample output:

1 1 0 0 1 1
16 36 41 45 49 34 29
42 54 47 60 59 15 15 24 48 54
0
0
1 0 0
0 1 1
1 7 12 3 3 6 11
14 11 14 13 13
1 1 1 1 1 0 1 0

Ranking

Ruby _

Perl _

Python _

JavaScript _

BASIC _

J _

C _

OCaml _

AWK _

R _

Language Ranking_

return to the top page