Graphs: BFS / DFS / Topological Sort

// BuildGraph turns an edge list into an adjacency list (undirected: store both directions).
// For a directed graph, drop the second append.
func BuildGraph(n int, edges [][]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
}

// BFS visits nodes in rings around start: a queue plus a visited set.
func BFS(adj [][]int, start int) []int {
	if start < 0 || start >= len(adj) {
		return nil
	}
	visited := make([]bool, len(adj))
	order := []int{}
	queue := []int{start}
	visited[start] = true // mark when ENQUEUED, not when dequeued
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		order = append(order, node)
		for _, next := range adj[node] {
			if !visited[next] {
				visited[next] = true
				queue = append(queue, next)
			}
		}
	}
	return order
}

// DFS dives as deep as possible before backing up: recursion is the stack.
func DFS(adj [][]int, start int) []int {
	if start < 0 || start >= len(adj) {
		return nil
	}
	visited := make([]bool, len(adj))
	order := []int{}
	var visit func(node int)
	visit = func(node int) {
		visited[node] = true
		order = append(order, node)
		for _, next := range adj[node] {
			if !visited[next] {
				visit(next)
			}
		}
	}
	visit(start)
	return order
}

// NumIslands: every cell is a node, its 4 neighbours are the edges.
// Each unvisited land cell starts a new island; DFS sinks the whole island.
func NumIslands(grid [][]byte) int {
	count := 0
	var sink func(r, c int)
	sink = func(r, c int) {
		if r < 0 || c < 0 || r >= len(grid) || c >= len(grid[r]) || grid[r][c] != '1' {
			return
		}
		grid[r][c] = '0' // mark visited by overwriting (the grid is our visited set)
		sink(r+1, c)
		sink(r-1, c)
		sink(r, c+1)
		sink(r, c-1)
	}
	for r := range grid {
		for c := range grid[r] {
			if grid[r][c] == '1' {
				count++
				sink(r, c)
			}
		}
	}
	return count
}

// CountComponents: how many separate groups does an undirected graph have?
// One traversal per unvisited node; each traversal covers exactly one group.
func CountComponents(n int, edges [][]int) int {
	adj := BuildGraph(n, edges)
	visited := make([]bool, n)
	var dfs func(node int)
	dfs = func(node int) {
		visited[node] = true
		for _, next := range adj[node] {
			if !visited[next] {
				dfs(next)
			}
		}
	}
	count := 0
	for i := 0; i < n; i++ {
		if !visited[i] {
			count++
			dfs(i)
		}
	}
	return count
}

// ShortestPath: fewest edges from src to dst in an unweighted graph, or -1 if unreachable.
// BFS reaches nodes in order of distance, so the first time we see dst is the shortest.
func ShortestPath(adj [][]int, src, dst int) int {
	if src < 0 || dst < 0 || src >= len(adj) || dst >= len(adj) {
		return -1
	}
	dist := make([]int, len(adj))
	for i := range dist {
		dist[i] = -1 // -1 doubles as "not visited"
	}
	dist[src] = 0
	queue := []int{src}
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		if node == dst {
			return dist[node]
		}
		for _, next := range adj[node] {
			if dist[next] == -1 {
				dist[next] = dist[node] + 1
				queue = append(queue, next)
			}
		}
	}
	return -1
}

// CanFinish: Kahn's topological sort. prerequisites[i] = {course, mustTakeFirst}.
// Repeatedly take courses with no unmet prerequisites; if some are never taken, there is a cycle.
func CanFinish(numCourses int, prerequisites [][]int) bool {
	adj := make([][]int, numCourses)
	indegree := make([]int, numCourses)
	for _, p := range prerequisites {
		adj[p[1]] = append(adj[p[1]], p[0]) // edge: prerequisite -> course
		indegree[p[0]]++
	}
	queue := []int{}
	for i, d := range indegree {
		if d == 0 {
			queue = append(queue, i)
		}
	}
	taken := 0
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		taken++
		for _, next := range adj[node] {
			indegree[next]--
			if indegree[next] == 0 {
				queue = append(queue, next)
			}
		}
	}
	return taken == numCourses
}

// HasCycle: does a DIRECTED graph contain a cycle? DFS with three colours.
// 0 = unvisited, 1 = on the current path, 2 = fully explored. Meeting a 1 means a back edge.
func HasCycle(adj [][]int) bool {
	state := make([]int, len(adj))
	var dfs func(node int) bool
	dfs = func(node int) bool {
		state[node] = 1
		for _, next := range adj[node] {
			if state[next] == 1 || (state[next] == 0 && dfs(next)) {
				return true
			}
		}
		state[node] = 2
		return false
	}
	for i := range adj {
		if state[i] == 0 && dfs(i) {
			return true
		}
	}
	return false
}

// Node is the graph node used by clone-graph style problems.
type Node struct {
	Val       int
	Neighbors []*Node
}

// CloneGraph: the map from old node to its copy is also the visited set.
func CloneGraph(node *Node) *Node {
	if node == nil {
		return nil
	}
	copies := map[*Node]*Node{}
	var clone func(n *Node) *Node
	clone = func(n *Node) *Node {
		if c, ok := copies[n]; ok {
			return c
		}
		c := &Node{Val: n.Val}
		copies[n] = c // register BEFORE recursing, or cycles recurse forever
		for _, nb := range n.Neighbors {
			c.Neighbors = append(c.Neighbors, clone(nb))
		}
		return c
	}
	return clone(node)
}

// LadderLength: words are nodes, and two words are connected when they differ by one letter.
// BFS from beginWord counts the fewest words in a transformation sequence. Neighbours are found by trying all
// 26 letters in each position and keeping those in the word list; each word is removed once seen.
func LadderLength(beginWord, endWord string, wordList []string) int {
	words := make(map[string]bool, len(wordList))
	for _, w := range wordList {
		words[w] = true
	}
	if !words[endWord] {
		return 0
	}
	queue := []string{beginWord}
	delete(words, beginWord)
	for steps := 1; len(queue) > 0; steps++ {
		for size := len(queue); size > 0; size-- {
			cur := queue[0]
			queue = queue[1:]
			if cur == endWord {
				return steps
			}
			b := []byte(cur)
			for i := range b {
				orig := b[i]
				for ch := byte('a'); ch <= 'z'; ch++ {
					b[i] = ch
					if next := string(b); words[next] {
						delete(words, next) // visited
						queue = append(queue, next)
					}
				}
				b[i] = orig
			}
		}
	}
	return 0
}