結果

問題 No.1640 簡単な色塗り
ユーザー 小野寺健
提出日時 2021-12-17 13:09:26
言語 Go
(1.23.4)
結果
MLE  
実行時間 -
コード長 1,130 bytes
コンパイル時間 15,649 ms
コンパイル使用メモリ 227,084 KB
実行使用メモリ 744,236 KB
最終ジャッジ日時 2024-09-14 14:04:03
合計ジャッジ時間 20,027 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 MLE * 1 -- * 51
権限があれば一括ダウンロードができます

ソースコード

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

package main
import (
    "fmt"
    "bufio"
    "os"
)
var N int
var G [][]int
var match []int
var used []bool
func main() {
    r := bufio.NewReader(os.Stdin)
    w := bufio.NewWriter(os.Stdout)
    defer w.Flush()
    fmt.Fscan(r, &N)
    G = make([][]int, 2*N)
    match = make([]int, 2*N)
    for i := 0; i < 2*N; i++ {
        G[i] = make([]int, 0, N)
        match[i] = -1
    }
    used = make([]bool, 2*N)
    for i := 0; i < N; i++ {
        var a, b int
        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 int, v int) {
    G[u] = append(G[u], v)
    G[v] = append(G[v], u)
}
func dfs(v int) 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() int {
    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