Rezultati

Up. imeNalogaJezikRezultatČas oddaje
ocetje-interneta-2019 Barvanje drevesa Python 3 100/100OK 24. apr '19 @ 20:07

Test Točke Porabljen spomin Porabljen čas Status
#1 [več] 10/10 8,680 MiB 0,000 s OK
#2 [več] 10/10 8,668 MiB 0,000 s OK
#3 [več] 10/10 8,680 MiB 0,000 s OK
#4 [več] 10/10 8,520 MiB 0,000 s OK
#5 [več] 10/10 8,609 MiB 0,000 s OK
#6 [več] 10/10 8,750 MiB 0,000 s OK
#7 [več] 10/10 8,895 MiB 0,000 s OK
#8 [več] 10/10 9,195 MiB 0,000 s OK
#9 [več] 10/10 9,297 MiB 0,000 s OK
#10 [več] 10/10 8,758 MiB 0,000 s OK

Ocenjevani program (barve.py):
n = int(input())

nodes = []
degrees = [0 for i in range(n+1)]
colored = [None for i in range(n)]

for i in range(n):
    nodes.append(list(map(int, input().split(' '))))
    a, b = nodes[i]

    degrees[a] += 1
    degrees[b] += 1


root = 0

for i in range(1, n+1):
    if degrees[i] == 0:
        root = i

leftmost = [None for i in range(n*2)]

def get_color(leftmost, depth):

    colors = set([1, 2, 3]) - set([leftmost[depth-1], leftmost[depth]])
    return colors.pop()


def dfs(x, depth):
    colored[x-1] = get_color(leftmost, depth)
    leftmost[depth] = get_color(leftmost, depth)


    if not nodes[x-1][0] == 0:
        dfs(nodes[x-1][0], depth+1)

    if not nodes[x-1][1] == 0:
        dfs(nodes[x-1][1], depth+1)



dfs(root, 1)


print(' '.join(map(str, colored)))