Parenting

A node in a tree eitherhas a parent ordoes not have a parent. It is never its own parent. You default your values to:

node_parent[child] = child

But it would be cleaner to keep them asNone. That way, your iteration onparents() would've just been:

def parents(ar, idx):    while ar[idx] is not None:        yield ar[idx]        idx = ar[idx]

Children

You usechild andparent in a lot of places where neither makes sense. For example:

for child, parent in enumerate(node_count):

There is nochild/parent relationship in that loop. That's confusing. Furthermore, you don't even use theparent part since what you're doing is just iterating over the nodes:

for node in xrange(N):    if node_count[node] % 2 = 0 and node_parent[node] is not None:        res += 1

But, more generally...

Global Variables and Data Storage

This solution half-relies on global variables (update_child_count) and half on passing around arguments (parents). It also involves keeping two separate arrays (node_parent andnode_count) when there really should be just the one array of both items. It'd be better to better to group these into a class:Node. ANode has two things: a size and a parent:

class Node(object):    def __init__(self):        self.parent = None        self.size = 1 #itself

And it has a way to set its parent - copying the loop I indicated above:

    def add_parent(self, p):        self.parent = p        while p is not None:            p.size += 1            p = p.parent

This simplifies your algorithm drastically. Now instead of keepingtwo lists, we just have to keep one:

nodes = [Node() for _ in xrange(N)]

And when we input thechild andparent^†, we just assign as appropriate:

nodes[child-1].add_parent(nodes[parent-1])

This is more direct than having two functions to do the updating. Then, all we need to do is find all the non-root nodes that have an even size, as you did before. Full solution using your same algo:

class Node(object):    def __init__(self):        self.parent = None        self.size = 1    def add_parent(self, p):        self.parent = p        while p is not None:            p.size += 1            p = p.parentif __name__ == '__main__':    N, E = map(int, raw_input().split())    nodes = [Node() for _ in xrange(N)]    for _ in xrange(E):        child, parent = map(int, raw_input().split())        nodes[child-1].add_parent(nodes[parent-1])    print sum(1 for node in nodes              if node.size % 2 == 0 and node.parent is not None)

^† I'm not convinced that you can necessarily be sure that thechild goes first in the inputs. It's not stipulated in the problem and this approach does require that to be true.

• \$\begingroup\$You can lookhere, the idea is taken fromUnionFind algorithm. Here initially each node is its own parent.\$\endgroup\$

  CodeYogi

  – CodeYogi

  2015-09-29 19:12:25 +00:00

  CommentedSep 29, 2015 at 19:12

• Use a space either side of operators, unless it's to show precedence. E.G.[None] * N and2*3 + 1.
• Don't have white space after non-white space on a line.node_count[parent] += 1.
• Use_ to 'void' unused output.for _ in xrange(E):.
• Use descriptive names,E ->EDGES.
• Reduce the size of theif __name__=='__main__', put it in a function for example.
• Don't use functions without using the designed output,enumerate(node_parent) instead ofxrange.You want to loop through the indexes, not the values.
• Consider using a class.Rather than passing variables, useself.
• Consider using a 2D array.Then you can pass one variable, and initialise the list with ease.

  [[child, 1] for child in xrange(N)]

Whileenumerate is good, please, just usexrange. It gives much better intent.

As you could probably guess explicit values are better than implicit values.(You changed the code in the question.)One way to makenode_parent andnode_count explicit is to make a basic closure. (May be the wrong name)

def make_update_child_count(node_parent, node_count):    def update_child_count(child):        for parent in parents(node_parent, child):            node_count[parent] += 1    return update_child_countupdate_child_count = make_update_child_count(node_parent, node_counter)

To be honest, it's quite long winded, and so you may want to use a class instead.But for a lazy explicit approach it works.And is much nicer than passing the same value again and again.And also makes the desired use of the function more explicit.

However if you change your code to use two classes, Node and Tree. And follow most of the above. You will see:

• for child, parent in enumerate(node_parent): can be implemented in theTree class. (In a list comprehension.)
• get_parents should be part of theNode class.
• for node in xrange(E): should be merged withupdate_child_count.
• There is no need forres androot.
• And most of all, you can describe the whole thing better.As classes are good for Trees.

I think you should use a pointer rather than the node list, to find/hold the parent.By default it should be None, to make it more like standard Node implementations.Also you should use this to make a generator unreliant on the node list forget_parents.

class Node(object):    def __init__(self, index):        self.parent = None        self.amount = 1    def get_parents(self):        parent = self.parent        while parent is not None:            yield parent            parent = parent.parent

I think you can have myTree class in themain, but for a better design I kept the code split.

First, the tree is based around the node list.So I would make it at initialization, using a list comprehension.And have it handle how your nodes are 'added' viaupdate_child_count/add_node.

class Tree(object):    def __init__(self, size):        self.nodes = [Node(i) for i in xrange(size)]    def add_node(self, child, parent):        self.nodes[child].parent = self.nodes[parent]        for parent_ in self.nodes[child].get_parents():            parent_.amount += 1

Finally I think that the main should be for the algorithm that is mostly abstracted, and for user input.Also you should use a generator comprehension with sum, to getret in one line.And you would be left with the following.

def main():    VERTICES, EDGES = map(int, raw_input().split())    tree = Tree(VERTICES)    for _ in xrange(EDGES):        tree.add_node(*[int(i) - 1 for i in raw_input().split()])    print sum(1 for node in tree.nodes[1:] if node.amount % 2 == 0)

Now you can easily see what each stage is doing, with simple algorithms.And it's properly split into sections that handle only one aspect of the program.

Also it's the same algorithm, but using classes, as trees probably should.

• python
• algorithm
• programming-challenge
• python-2.x