結果

問題 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 #
raw source code 

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
}
0