結果

問題 No.1640 簡単な色塗り
ユーザー 小野寺健
提出日時 2021-12-18 10:05:01
言語 Go
(1.23.4)
結果
TLE  
実行時間 -
コード長 1,151 bytes
コンパイル時間 15,515 ms
コンパイル使用メモリ 238,664 KB
実行使用メモリ 13,760 KB
最終ジャッジ日時 2024-09-15 10:31:47
合計ジャッジ時間 22,016 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 TLE * 1 -- * 51
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package main
import (
    "fmt"
    "bufio"
    "os"
)
var N int32
var G [][]int32
var match []int32
var used []bool
func main() {
    r := bufio.NewReader(os.Stdin)
    w := bufio.NewWriter(os.Stdout)
    defer w.Flush()
    fmt.Fscan(r, &N)
    G = make([][]int32, 2*N)
    match = make([]int32, 2*N)
    var i int32
    for i = 0; i < 2*N; i++ {
        match[i] = -1
    }
    used = make([]bool, 2*N)
    for i = 0; i < N; i++ {
        var a, b int32
        fmt.Fscan(r, &a, &b)
        add_edge(i, a + N - 1)
        add_edge(i, b + N - 1)
    }
    n := bipartite_matching()
    if n == N {
        fmt.Fprintln(w, "Yes")
        for i = 0; i < N; i++ {
            fmt.Fprintln(w, match[i] - N + 1)
        }
    } else {
        fmt.Fprintln(w, "No")
    }
}
func add_edge(u int32, v int32) {
    G[u] = append(G[u], v)
    G[v] = append(G[v], u)
}
func dfs(v int32) bool {
    used[v] = true
    for _, u := range G[v] {
        w := match[u]
        if w < 0 || (!used[w] && dfs(w)) {
            match[v] = u
            match[u] = v
            return true
        }
    }
    return false
}
func bipartite_matching() int32 {
    var res, v, i int32
    res = 0
    for v = 0; v < 2 * N; v++ {
        if match[v] < 0 {
            for i = 0; i < 2*N; i++ {
                used[i] = false
            }
            if dfs(v) {
                res++;
            }
        }
    }
    return res
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0