/
even-tree.py
67 lines (52 loc) · 1.72 KB
/
even-tree.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
# Even Tree
# Developer: Murillo Grubler
# https://www.hackerrank.com/challenges/even-tree/problem
class Node(object):
def __init__(self, value=None):
self._value = value
self._parent = None
self._descendant = 0
def set_parent(self, parent_val):
self._parent = parent_val
ancestor = parent_val
while (ancestor != None):
ancestor._descendant += 1
ancestor = ancestor.parent
def get_parent(self):
return self._parent
def set_descendant(self, descendant):
self._descendant = descendant
def get_descendant(self):
return self._descendant
def set_value(self, value):
self._value = value
def get_value(self):
return self._value
@staticmethod
def find_parent(nodes, parent):
for node in nodes:
if node.value == parent:
return node
return None
parent = property(get_parent, set_parent)
descendant = property(get_descendant, set_descendant)
value = property(get_value, set_value)
edges_removeds = 0
nodes = []
n, m = input().strip().split(' ')
for i in range(int(m)):
children, parent = [int(node) for node in input().strip().split(' ')]
if i == 0:
node_parent = Node(parent)
nodes.append(node_parent)
node_children = Node(children)
node_children.parent = node_parent
nodes.append(node_children)
else:
node_children = Node(children)
node_children.parent = Node.find_parent(nodes, parent)
nodes.append(node_children)
for node in nodes:
if node.value > 1 and node.descendant > 0 and node.descendant % 2 == 1:
edges_removeds += 1
print (edges_removeds)