1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
package graph
// Bipartition returns a subset U of g's vertices with the property
// that every edge of g connects a vertex in U to one outside of U.
// If g isn't bipartite, it returns an empty slice and sets ok to false.
func Bipartition(g Iterator) (part []int, ok bool) {
type color byte
const (
none color = iota
white
black
)
colors := make([]color, g.Order())
whiteCount := 0
for v := range colors {
if colors[v] != none {
continue
}
colors[v] = white
whiteCount++
for queue := []int{v}; len(queue) > 0; {
v := queue[0]
queue = queue[1:]
if g.Visit(v, func(w int, _ int64) (skip bool) {
switch {
case colors[w] != none:
if colors[v] == colors[w] {
skip = true
}
return
case colors[v] == white:
colors[w] = black
default:
colors[w] = white
whiteCount++
}
queue = append(queue, w)
return
}) {
return []int{}, false
}
}
}
part = make([]int, 0, whiteCount)
for v, color := range colors {
if color == white {
part = append(part, v)
}
}
return part, true
}
|
