Graph

Submit

Your name:
File:
Open code-statistics:

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.


I've removed trailing whitespaces from 2nd output -- shinh

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 _

RankUserSizeTimeDateStatistics
1yvl1660.24682011/01/26 14:24:310B / 79B / 75B

Perl _

RankUserSizeTimeDateStatistics
1tails1130.00182011/01/25 21:38:5545B / 19B / 38B
2%20(tails)1110.01722015/08/05 19:13:0545B / 19B / 36B

Python _

RankUserSizeTimeDateStatistics
1hallvabo (embed)1270.05362011/01/20 05:07:3851B / 42B / 30B
2recursive1590.06122011/01/21 01:57:250B / 89B / 61B
3recursive (embed)1600.05572011/01/20 04:36:560B / 90B / 17B
4hallvabo1670.12432011/01/20 08:49:570B / 94B / 61B
5gre4180.06322011/01/16 09:54:0416B / ?B / ?B

JavaScript _

RankUserSizeTimeDateStatistics
1nn1780.14292011/01/21 12:59:040B / 88B / 86B
2nn(inconsistent. 2nd output has trailing SPs.)2090.15022011/01/10 17:49:300B / 100B / 105B

BASIC _

RankUserSizeTimeDateStatistics
1pooq1620.00152011/01/16 15:20:210B / 94B / 11B

J _

RankUserSizeTimeDateStatistics
1I., S.(thx4smpltreatmnt>shinh)580.07402011/01/24 06:10:570B / 15B / 41B

C _

RankUserSizeTimeDateStatistics
1nn1790.00222011/02/04 00:14:170B / 81B / 96B
2nai1880.00212011/01/17 21:23:380B / 86B / 100B
3not1920.00212011/01/18 01:15:030B / 90B / 102B
4yuyarin1930.00162011/01/16 10:45:020B / 90B / 103B

OCaml _

RankUserSizeTimeDateStatistics
1m.ukai1900.06432011/01/21 18:11:240B / 110B / 23B

AWK _

RankUserSizeTimeDateStatistics
1I., S.1530.01942011/01/25 18:43:410B / 68B / 81B

R _

RankUserSizeTimeDateStatistics
1pooq1570.60232011/01/28 16:08:140B / 91B / 12B

Language Ranking_

RankLangUserSizeScore
1JI., S.(thx4smpltreatmnt>shinh)5810000
2Perl%20(tails)1115225
3Pythonhallvabo (embed)1274566
4AWKI., S.1533790
5Rpooq1573694
6BASICpooq1623580
7Rubyyvl1663493
8JavaScriptnn1783258
9Cnn1793240
10OCamlm.ukai1903052

return top