D - Coloring Edges on Tree

https://atcoder.jp/contests/abc146/tasks/abc146_d

問題概要

木がある。頂点同士を結ぶ辺に色を塗りたい。各頂点が接する辺の中で、色の被りがないようにしたい。使用する色の種類が最小になる組み合わせを求めよ。

考え方

各頂点の次数を考えれる。頂点が接している辺に、1~次数までの数字を振っていけばいい。

type Node struct {
    to, edgeId int
}
var tree [][]Node
var dp []int

func solve() {
    n := getInt()
    tree = make([][]Node, n)
    for i := 0; i < n-1; i++ {
        in := getInts()
        a, b := in[0]-1, in[1]-1
        tree[a] = append(tree[a], Node{b, i})
        tree[b] = append(tree[b], Node{a, i})
    }

    dp = make([]int, n - 1)

    dfs(0, -1, -1)

    fmt.Println(max(dp...))
    for i := 0; i < n - 1; i++ {
        fmt.Println(dp[i])
    }
}

func dfs(node, color, parent int) {
    tmp := 1
    for _, next := range tree[node] {
        if next.to == parent {
            continue
        }
        // 自分と同じ色は使わない
        if tmp == color {
            tmp++
        }
        dp[next.edgeId] = tmp
        tmp++

        dfs(next.to, dp[next.edgeId], node)
    }
}

https://atcoder.jp/contests/abc146/submissions/53713713

hxrxchang / atcoder

D - Coloring Edges on Tree #59

問題概要

考え方