"Even Tree" Python implementation

Problem Statement


You are given a tree (a simple connected graph with no cycles). You have to remove as many edges from the tree as possible to obtain a forest with the condition that : Each connected component of the forest should contain an even number of vertices.


To accomplish this, you will remove some edges from the tree. Find out the number of removed edges.

Input Format


The first line of input contains two integers N and M. N is the number of vertices and M is the number of edges.
The next M lines contain two integers ui and vi which specifies an edge of the tree. (1-based index)

Output Format


Print the answer, a single integer.

Constraints


\$2 \le N \le 100\$

Example input

10 9
2 1
3 1
4 3
5 2
6 1
7 2
8 6
9 8
10 8

Example output


2

Note: The tree in the input will be such that it can always be decomposed into components containing even number of nodes.

Solution

def parents(ar, child):
    """ Enumerates on the list of all the parents of a child."""
    parent = ar[child]
    while child != parent:
        yield parent
        child = parent
        parent = ar[child]

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

if __name__ == '__main__':

    N, E = map(int, raw_input().split())
    node_count = [None]*N
    node_parent = [None]*N
    root = 0
    res = 0
    for child, parent in enumerate(node_parent):
        node_parent[child] = child
        node_count[child] = 1

    for node in xrange(E):
        child, parent = map(int, raw_input().split())
        node_parent[child-1] = parent-1
        update_child_count(node_parent, node_count, child-1)

    for child, parent in enumerate(node_count):
        if node_count[child] % 2 == 0 and child != root:
            res += 1

    print res

The solution is working fine, but I am more interested in a better/more efficient approach.

Parenting

A node in a tree either has a parent or does 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 as None. That way, your iteration on parents() would've just been:

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

Children

You use child and parent in a lot of places where neither makes sense. For example:

for child, parent in enumerate(node_count):

There is no child/parent relationship in that loop. That's confusing. Furthermore, you don't even use the parent 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 and node_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. A Node 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 keeping two lists, we just have to keep one:

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

And when we input the child and parent†, 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.parent

if __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 the child goes first in the inputs. It's not stipulated in the problem and this approach does require that to be true.

StackExchange Code Review Q#105999, answer score: 3