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
Only available for Pro members
Pro onlyBinary search and monotone answer
Only available for Pro members
Pro onlyPointers and sliding window
Only available for Pro members
Pro onlyPrefix, difference, and hashed state
Only available for Pro members
Pro onlyStack and monotone deque
Only available for Pro members
Pro onlyHeap, selection, and stream
Only available for Pro members
Pro onlyGreedy and scheduling
Only available for Pro members
Pro onlyDivide and conquer
Only available for Pro members
Pro onlyDynamic programming
Only available for Pro members
Pro onlyBacktracking and constraint search
Only available for Pro members
Pro onlyTree, BST, and trie
Only available for Pro members
Pro onlyDSU, MST, and offline activation
Only available for Pro members
Pro onlyRange-query data structures
Only available for Pro members
Pro onlyString matching, hashing, and palindrome
Only available for Pro members
Pro onlyMath, number theory, and combinatorics
Only available for Pro members
Pro onlyBit manipulation and bitmask state
Only available for Pro members
Pro onlyGeometry, sweep, simulation, and parsing
Only available for Pro members