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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
package graph
// Connected tells if g has exactly one (weakly) connected component.
func Connected(g Iterator) bool {
_, count := components(g)
return count == 1
}
// Components produces a partition of g's vertices into its
// (weakly) connected components.
func Components(g Iterator) [][]int {
sets, count := components(g)
m := make([][]int, g.Order())
for v := range m {
x := sets.find(v)
m[x] = append(m[x], v)
}
components := make([][]int, 0, count)
for _, comp := range m {
if comp != nil {
components = append(components, comp)
}
}
return components
}
func components(g Iterator) (sets disjointSets, count int) {
n := g.Order()
sets, count = makeSingletons(n), n
for v := 0; v < n && count > 1; v++ {
g.Visit(v, func(w int, _ int64) (skip bool) {
x, y := sets.find(v), sets.find(w)
if x != y {
sets.union(x, y)
count--
if count == 1 {
skip = true
}
}
return
})
}
return
}
// Union-find with path compression performs any sequence of m ≥ n find
// and n – 1 union operations in O(m log n) time. Union by rank doesn't
// seem to improve performance here.
type disjointSets []int
func makeSingletons(n int) disjointSets {
p := make(disjointSets, n)
for v := range p {
p[v] = v
}
return p
}
func (p disjointSets) find(x int) int {
root := x
for root != p[root] {
root = p[root]
}
for p[x] != root {
p[x], x = root, p[x]
}
return root
}
func (p disjointSets) union(x, y int) {
x, y = p.find(x), p.find(y)
if x != y {
p[y] = x
}
}
|
