hackerrank: All Domains ↠ Algorithms ↠ Graph Theory ↠ Even Tree

even-tree.py

#!/usr/bin/python
# -*- encoding: utf-8 -*-
# pylint: disable=invalid-name,missing-docstring,bad-builtin,star-args
from collections import defaultdict

def numberOfBreaks(graph):
    bks = [0]
    visited = set()
    def recur(i):
        visited.add(i)
        if len(graph[i]) == 1 and graph[i][0] in visited:
            return 1
        children = 0
        for x in graph[i]:
            if x not in visited:
                y = recur(x)
                if y % 2 == 0:
                    bks[0] += 1
                else:
                    children += y
        return children + 1

    recur(graph.iterkeys().next())
    return bks[0]

def main():
    n, m = map(int, raw_input().split())
    edges = defaultdict(list)
    for _ in xrange(m):
        p, q = map(int, raw_input().split())
        edges[p].append(q)
        edges[q].append(p)
    print numberOfBreaks(edges)

main()