結果

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

ソースコード

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

package main
import (
    "fmt"
    "bufio"
    "os"
)
type Cell struct {
    item int32
    next *Cell
}
type CellMgr struct {
    top, cp, last *Cell
}
func (this *CellMgr) append(item int32) {
    ncp := new(Cell)
    ncp.item = item
    if this.top == nil {
        this.top = ncp
        this.cp = ncp
        this.last = ncp
    } else {
        this.last.next = ncp
        this.last = ncp
    }
}
func (this *CellMgr) isNext() bool {
    return this.cp != this.last
}
func (this *CellMgr) next() (int32, bool) {
    cp := this.cp
    if cp != nil {
        this.cp = cp.next
        return cp.item, true
    } else {
        return 0, false
    }
}
var N int32
var G []*CellMgr
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([]*CellMgr, 2*N)
    match = make([]int32, 2*N)
    var i int32
    for i = 0; i < 2*N; i++ {
        G[i] = new(CellMgr)
        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(v)
    G[v].append(u)
}
func dfs(v int32) bool {
    used[v] = true
    for G[v].isNext() {
        u, _ := G[v].next()
        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