二部グラフ最大マッチング

 1func bipartiteMatching(g [][]int) (int, []int) {
 2	used := make([]int, len(g))
 3	match := make([]int, len(g))
 4	for i := 0; i < len(g); i++ {
 5		match[i] = -1
 6	}
 7	cnt := 0
 8
 9	var fn func(v int) bool
10	fn = func(v int) bool {
11		if used[v] == cnt {
12			return false
13		}
14		used[v] = cnt
15		for _, to := range g[v] {
16			if match[to] == -1 || fn(match[to]) {
17				match[v], match[to] = to, v
18				return true
19			}
20		}
21		return false
22	}
23
24	res := 0
25
26	for i := 0; i < len(g); i++ {
27		cnt++
28		if match[i] == -1 && fn(i) {
29			res++
30		}
31	}
32
33	return res, match
34}
35