FreeDFS Components and Reachability
- Recognition
- The prompt speaks about connected, reachable, component, group, or region. · It asks whether a state is reachable or how many groups exist, not for the fewest steps.
- Invariant
- Once marked visited, a vertex belongs to the component represented by the current search and can never join a later component.
- Complexity
- O(V+E) time · O(V) space
def components(graph):
seen, groups = set(), []
for start in graph:
if start in seen:
continue
seen.add(start)
stack, group = [start], []
while stack:
u = stack.pop()
group.append(u)
for v in graph[u]:
if v not in seen:
seen.add(v)
stack.append(v)
groups.append(group)
return groups
FreeBFS Connectivity Traversal
- Recognition
- The core task is graph or implicit-state traversal, not weighted optimization. · Avoiding recursive depth is important.
- Invariant
- Every queued vertex is discovered and assigned to the current component but not fully expanded; an unseen vertex is not yet proven reachable from this start.
- Complexity
- O(V+E) time · O(V) space
from collections import deque
def bfs_groups(graph):
seen, label = set(), {}
group_id = 0
for start in graph:
if start in seen:
continue
seen.add(start)
q = deque([start])
while q:
u = q.popleft()
label[u] = group_id
for v in graph[u]:
if v not in seen:
seen.add(v)
q.append(v)
group_id += 1
return group_id, label
FreeGrid Flood Fill
- Recognition
- The input is a grid, image, or board with local moves. · The story mentions islands, regions, colors, holes, or boundaries.
- Invariant
- Every cell in the frontier has passed bounds and predicate checks and is already marked; expansion only considers its eligible neighbors.
- Complexity
- O(RC) time · O(RC) space
from collections import deque
def flood(grid, sr, sc, target, replacement):
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
if not (0 <= sr < rows and 0 <= sc < cols):
return 0
if target == replacement or grid[sr][sc] != target:
return 0
q = deque([(sr, sc)])
grid[sr][sc] = replacement
area = 0
while q:
r, c = q.popleft()
area += 1
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
if grid[nr][nc] == target:
grid[nr][nc] = replacement
q.append((nr, nc))
return area
FreeTopological Sort / Indegree Elimination
- Recognition
- The story uses prerequisite, dependency, or build order. · A permutation satisfying all precedence constraints is requested.
- Invariant
- Every frontier vertex has zero indegree in the remaining graph; outputting u changes only the indegrees of u's direct successors.
- Complexity
- O(V+E) time · O(V+E) space
from collections import deque
def topo_order(nodes, edges):
graph = {u: [] for u in nodes}
indeg = {u: 0 for u in nodes}
for u, v in edges:
graph[u].append(v)
indeg[v] += 1
q = deque(u for u in nodes if indeg[u] == 0)
order = []
while q:
u = q.popleft()
order.append(u)
for v in graph[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return order if len(order) == len(nodes) else None
Next families
Pro onlyOrdered frontier and path
Pro onlyBinary search and monotone answer
Pro onlyPointers and sliding window
Pro onlyPrefix, difference, and hashed state
Pro onlyStack and monotone deque
Pro onlyHeap, selection, and stream
Pro onlyGreedy and scheduling
Pro onlyDivide and conquer
Pro onlyDynamic programming
Pro onlyBacktracking and constraint search
Pro onlyTree, BST, and trie
Pro onlyDSU, MST, and offline activation
Pro onlyRange-query data structures
Pro onlyString matching, hashing, and palindrome
Pro onlyMath, number theory, and combinatorics
Pro onlyBit manipulation and bitmask state
Pro onlyGeometry, sweep, simulation, and parsing