強連結成分分解

 1type scc struct {
 2	g  [][]int
 3	rg [][]int
 4}
 5
 6func newStronglyConnectedComponents(n int) *scc {
 7	return &scc{make([][]int, n), make([][]int, n)}
 8}
 9
10func (s *scc) AddEdge(v, to int) {
11	s.g[v] = append(s.g[v], to)
12	s.rg[to] = append(s.rg[to], v)
13}
14
15func (s *scc) Scc() [][]int {
16	n := len(s.g)
17	vs := make([]int, 0, n)
18	vis := make([]bool, n)
19	cmp := make([]int, n)
20
21	var dfs func(v int)
22	dfs = func(v int) {
23		vis[v] = true
24		for _, to := range s.g[v] {
25			if !vis[to] {
26				dfs(to)
27			}
28		}
29		vs = append(vs, v)
30	}
31
32	var rdfs func(v, k int)
33	rdfs = func(v, k int) {
34		vis[v] = true
35		cmp[v] = k
36		for _, to := range s.rg[v] {
37			if !vis[to] {
38				rdfs(to, k)
39			}
40		}
41	}
42
43	for i := 0; i < n; i++ {
44		if !vis[i] {
45			dfs(i)
46		}
47	}
48
49	for i := 0; i < n; i++ {
50		vis[i] = false
51	}
52
53	k := 0
54	for i := len(vs) - 1; i >= 0; i-- {
55		if !vis[vs[i]] {
56			rdfs(vs[i], k)
57			k++
58		}
59	}
60
61	t := make([][]int, k)
62	for i := 0; i < n; i++ {
63		t[cmp[i]] = append(t[cmp[i]], i)
64	}
65
66	return t
67}
68