"Even Tree" Python implementation

Question

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.

Answer 1

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.

• CodeYogi: You can look here, the idea is taken from UnionFind algorithm. Here initially each node is its own parent.

Answer 2

• Use a space either side of operators, unless it's to show precedence. E.G. [None] * N and 2*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 the if __name__=='__main__', put it in a function for example.
• Don't use functions without using the designed output, enumerate(node_parent) instead of xrange. You want to loop through the indexes, not the values.
• Consider using a class. Rather than passing variables, use self.
• Consider using a 2D array. Then you can pass one variable, and initialise the list with ease.

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

While enumerate is good, please, just use xrange. 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 make node_parent and node_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_count
update_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 the Tree class. (In a list comprehension.)
• get_parents should be part of the Node class.
• for node in xrange(E): should be merged with update_child_count.
• There is no need for res and root.
• 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 for get_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 my Tree class in the main, 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' via update_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 get ret 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.