src

Go monorepo.
git clone git://code.dwrz.net/src
Log | Files | Refs

scc.go (825B)

      1 // Copyright 2026 The Go Authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style
      3 // license that can be found in the LICENSE file.
      4 
      5 package graph
      6 
      7 import "slices"
      8 
      9 // SCCs computes the strongly connected components of the graph g.
     10 func SCCs[NodeID comparable](g Graph[NodeID]) [][]NodeID {
     11 	// Use Kosaraju's algorithm. Tarjan is overkill here.
     12 
     13 	// Forward pass
     14 	S := Postorder(g)
     15 
     16 	// Reverse pass
     17 	gt := Transpose(g)
     18 	seen := make(map[NodeID]bool)
     19 	var scc []NodeID
     20 	var sccs [][]NodeID
     21 	var rvisit func(NodeID)
     22 	rvisit = func(u NodeID) {
     23 		if !seen[u] {
     24 			seen[u] = true
     25 			scc = append(scc, u)
     26 			for v := range gt.Out(u) {
     27 				rvisit(v)
     28 			}
     29 		}
     30 	}
     31 	for _, root := range slices.Backward(S) {
     32 		if !seen[root] {
     33 			scc = nil
     34 			rvisit(root)
     35 			sccs = append(sccs, scc)
     36 		}
     37 	}
     38 	return sccs
     39 }