Graph structure: cycles, SCCs, bridges & cloning

package main
 
import "fmt"
 
const (
	white = iota
	gray
	black
)
 
// findCycle returns one directed cycle, or nil if the graph is acyclic.
func findCycle(adj [][]int) []int {
	color := make([]int, len(adj))
	parent := make([]int, len(adj))
	var cycle []int
	var dfs func(u int) bool
	dfs = func(u int) bool {
		color[u] = gray
		for _, v := range adj[u] {
			switch color[v] {
			case gray: // back edge: walk parents from u back to v
				cycle = []int{v}
				for x := u; x != v; x = parent[x] {
					cycle = append([]int{x}, cycle...)
				}
				cycle = append([]int{v}, cycle...)
				return true
			case white:
				parent[v] = u
				if dfs(v) {
					return true
				}
			}
		}
		color[u] = black
		return false
	}
	for u := range adj {
		if color[u] == white && dfs(u) {
			return cycle
		}
	}
	return nil
}
 
func main() {
	dag := [][]int{{1, 2}, {2}, {}} // A->B, A->C, B->C: C is reached twice, no cycle
	fmt.Println("dag:", findCycle(dag))
	looped := [][]int{{1}, {2}, {3}, {1}, {}} // 1 -> 2 -> 3 -> 1
	fmt.Println("cycle:", findCycle(looped))
}

dag: []
cycle: [1 2 3 1]

package main
 
import "fmt"
 
func twoColor(adj [][]int) ([]int, bool) {
	color := make([]int, len(adj))
	for i := range color {
		color[i] = -1
	}
	for s := range adj { // the graph may have several components
		if color[s] != -1 {
			continue
		}
		color[s] = 0
		queue := []int{s}
		for len(queue) > 0 {
			u := queue[0]
			queue = queue[1:]
			for _, v := range adj[u] {
				if color[v] == -1 {
					color[v] = 1 - color[u]
					queue = append(queue, v)
				} else if color[v] == color[u] {
					return color, false // same color on both ends of an edge
				}
			}
		}
	}
	return color, true
}
 
func undirected(n int, edges [][2]int) [][]int {
	adj := make([][]int, n)
	for _, e := range edges {
		adj[e[0]] = append(adj[e[0]], e[1])
		adj[e[1]] = append(adj[e[1]], e[0])
	}
	return adj
}
 
func main() {
	square := undirected(4, [][2]int{{0, 1}, {1, 2}, {2, 3}, {3, 0}}) // even cycle
	fmt.Println(twoColor(square))
	triangle := undirected(3, [][2]int{{0, 1}, {1, 2}, {2, 0}}) // odd cycle
	_, ok := twoColor(triangle)
	fmt.Println("triangle bipartite:", ok)
}

[0 1 0 1] true
triangle bipartite: false

package main
 
import (
	"fmt"
	"slices"
)
 
func kosaraju(adj [][]int) [][]int {
	n := len(adj)
	seen := make([]bool, n)
	var order []int
	var dfs1 func(u int)
	dfs1 = func(u int) {
		seen[u] = true
		for _, v := range adj[u] {
			if !seen[v] {
				dfs1(v)
			}
		}
		order = append(order, u) // record on finish
	}
	for u := range n {
		if !seen[u] {
			dfs1(u)
		}
	}
 
	rev := make([][]int, n)
	for u, vs := range adj {
		for _, v := range vs {
			rev[v] = append(rev[v], u)
		}
	}
	comp := make([]int, n)
	for i := range comp {
		comp[i] = -1
	}
	var sccs [][]int
	var dfs2 func(u, id int)
	dfs2 = func(u, id int) {
		comp[u] = id
		sccs[id] = append(sccs[id], u)
		for _, v := range rev[u] {
			if comp[v] == -1 {
				dfs2(v, id)
			}
		}
	}
	for i := n - 1; i >= 0; i-- { // decreasing finish time
		if u := order[i]; comp[u] == -1 {
			sccs = append(sccs, nil)
			dfs2(u, len(sccs)-1)
		}
	}
	for _, c := range sccs {
		slices.Sort(c)
	}
	return sccs
}
 
func main() {
	// 0 -> 1 -> 2 -> 0 form a loop; 2 -> 3; 3 -> 4 -> 5 -> 3 form another; 5 -> 6
	adj := [][]int{{1}, {2}, {0, 3}, {4}, {5}, {3, 6}, {}}
	fmt.Println(kosaraju(adj))
}

[[0 1 2] [3 4 5] [6]]

package main
 
import "fmt"
 
func bridges(n int, edges [][2]int) [][2]int {
	adj := make([][]int, n)
	for _, e := range edges {
		adj[e[0]] = append(adj[e[0]], e[1])
		adj[e[1]] = append(adj[e[1]], e[0])
	}
	disc := make([]int, n)
	low := make([]int, n)
	timer := 0
	var out [][2]int
	var dfs func(u, parent int)
	dfs = func(u, parent int) {
		timer++
		disc[u], low[u] = timer, timer
		for _, v := range adj[u] {
			switch {
			case v == parent:
				continue
			case disc[v] != 0: // back edge to an ancestor
				low[u] = min(low[u], disc[v])
			default:
				dfs(v, u)
				low[u] = min(low[u], low[v])
				if low[v] > disc[u] {
					out = append(out, [2]int{u, v})
				}
			}
		}
	}
	for u := range n {
		if disc[u] == 0 {
			dfs(u, -1)
		}
	}
	return out
}
 
func main() {
	// A triangle 0-1-2, a bridge 1-3, then another triangle 3-4-5, and a tail 5-6.
	edges := [][2]int{{0, 1}, {1, 2}, {2, 0}, {1, 3}, {3, 4}, {4, 5}, {5, 3}, {5, 6}}
	fmt.Println("bridges:", bridges(7, edges))
}

bridges: [[5 6] [1 3]]

package main
 
import "fmt"
 
// --- Clone Graph ---
 
type GNode struct {
	Val       int
	Neighbors []*GNode
}
 
func cloneGraph(n *GNode) *GNode {
	copies := map[*GNode]*GNode{}
	var dfs func(*GNode) *GNode
	dfs = func(o *GNode) *GNode {
		if o == nil {
			return nil
		}
		if c, ok := copies[o]; ok {
			return c // already copied: reuse it (this is what stops cycles)
		}
		c := &GNode{Val: o.Val}
		copies[o] = c // register BEFORE recursing into neighbors
		for _, nb := range o.Neighbors {
			c.Neighbors = append(c.Neighbors, dfs(nb))
		}
		return c
	}
	return dfs(n)
}
 
// --- Copy List with Random Pointer ---
 
type LNode struct {
	Val          int
	Next, Random *LNode
}
 
func copyRandomList(head *LNode) *LNode {
	copies := map[*LNode]*LNode{nil: nil}
	for n := head; n != nil; n = n.Next { // pass 1: make every copy
		copies[n] = &LNode{Val: n.Val}
	}
	for n := head; n != nil; n = n.Next { // pass 2: wire Next and Random through the map
		copies[n].Next = copies[n.Next]
		copies[n].Random = copies[n.Random]
	}
	return copies[head]
}
 
func main() {
	// A square graph 1-2-3-4-1: every node is reachable two ways, and there is a cycle.
	n1, n2, n3, n4 := &GNode{Val: 1}, &GNode{Val: 2}, &GNode{Val: 3}, &GNode{Val: 4}
	n1.Neighbors = []*GNode{n2, n4}
	n2.Neighbors = []*GNode{n1, n3}
	n3.Neighbors = []*GNode{n2, n4}
	n4.Neighbors = []*GNode{n3, n1}
	c := cloneGraph(n1)
	fmt.Println("clone is a new node:", c != n1, " values:", c.Val, c.Neighbors[0].Val, c.Neighbors[1].Val)
	fmt.Println("cycle preserved:", c.Neighbors[0].Neighbors[0] == c) // 1 -> 2 -> back to the SAME clone of 1
 
	// List 7 -> 13 -> 11, randoms: 7->nil, 13->7, 11->7
	a, b, d := &LNode{Val: 7}, &LNode{Val: 13}, &LNode{Val: 11}
	a.Next, b.Next = b, d
	b.Random, d.Random = a, a
	cp := copyRandomList(a)
	for n := cp; n != nil; n = n.Next {
		r := "nil"
		if n.Random != nil {
			r = fmt.Sprint(n.Random.Val)
		}
		fmt.Printf("%d(random %s) ", n.Val, r)
	}
	fmt.Println("\nshares no nodes with the original:", cp != a && cp.Next != b && cp.Next.Random == cp)
}

clone is a new node: true  values: 1 2 4
cycle preserved: true
7(random nil) 13(random 7) 11(random 7) 
shares no nodes with the original: true