Count the Leaves

Computer Science Level 4

Here is the adjacency matrix of a (undirected) tree .

A vertex of a tree is a leaf , iff there is only one edge connected to it.

What is the number of leaves in the given tree?

Input Format and Constraints

  • The given tree is of 100 vertices.
  • There are 100 lines in the file with 100 space separated integers on each line.
  • If the j th j^\text{th} integer in the i th i^\text{th} line is 1, there is an edge connecting i i and j j . Otherwise, there is no such edge.


The answer is 49.

Agnishom Chattopadhyay by Agnishom Chattopadhyay , 22, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

The solution is straightforward. We check the degree for each node. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
 
import urllib2

g = map(lambda x: x.split(),urllib2.urlopen("http://pastebin.com/raw/AgHxr7jT").read().split('\r\n'))

def isLeaf(i):
    x = False
    for j in g[i]:
        if j == '1':
            if x == True:
                return False
            else:
                x = True
    return True

print sum(map(isLeaf,range(100)))

1 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...