OKTV 2017/18 turn 2 ex. 3

faszelso.py

from sys import stdin, stdout


def readTree(numNodes):
    """Does what it says on the box.
       The tree is stored like tree[n] = [...], the list of the child nodes of node n"""
    nodes = {}
    for i in range(1,numNodes+1):
        # Why would I write readable code?
        nodes[i] = list(map(int,stdin.readline().strip().split()[:-1]))
    return nodes

def BFS(tree, start, level = 1, firsts = {}, lasts = {}):
    """
    Iterate over the tree
    
    tree is the full tree
    start is the node currently processed
    level is the depth level of that node
    
    firsts is a {}, where we store the first node we processed in a specific level
    (it'll be the leftmost one)
    
    lasts is a {}, like first, but we store the last node of that level
    (the rightmost one)
    """
    
    # update the two dicts
    if level not in firsts:
        firsts[level] = start
    lasts[level] = start
    
    # Iterate over child nodes, increment level
    for n in tree[start]:
        BFS(tree, n, level+1, firsts, lasts)
    
    # As dicts are passed via reference, we now have the updated dicts.
    # Convert the values to a set to remove duplicate elements
    # list() is needed because {}.values() returns an iterator
    return set(list(firsts.values()) + list(lasts.values()))

# Did you know that (atleast in python)
# the access time of a global var is way bigger than
# the access time of a local?
# So because that, its a good idea to make everything a local
# by wrapping the main logic in a function
def main():
    N = int(stdin.readline())
    
    tree = readTree(N)
    res = BFS(tree, 1)
    
    
    print(len(res))
    print(" ".join(map(str, res)))
    
if __name__=='__main__':
    main()