結果

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

ソースコード

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

package main
import (
    "fmt"
    "bufio"
    "os"
    "strconv"
)
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() {
    sc := bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    sc.Scan()
    _N, _ := strconv.Atoi(sc.Text())
    N = int32(_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
        sc.Scan()
        _a, _ := strconv.Atoi(sc.Text())
        a = int32(_a)
        sc.Scan()
        _b, _ := strconv.Atoi(sc.Text())
        b = int32(_b)
        add_edge(i, a + N - 1)
        add_edge(i, b + N - 1)
    }
    n := bipartite_matching()
    if n == N {
        fmt.Println("Yes")
        for i = 0; i < N; i++ {
            fmt.Println(match[i] - N + 1)
        }
    } else {
        fmt.Println("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 int32
    res = 0
    for v = 0; v < 2 * N; v++ {
        if match[v] < 0 {
            used = make([]bool, 2*N)
            if dfs(v) {
                res++;
            }
        }
    }
    return res
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0