FreeDFS 连通块与可达性
- Recognition
- 题意出现 connected、reachable、component、group 或 region。 · 只问能否到达、分成几组或每组统计，不问最少步数。
- Invariant
- 节点一旦标记 visited，就已被归入当前搜索代表的分量，之后不会属于另一分量。
- 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 连通性遍历
- Recognition
- 核心是遍历图或隐式状态图，而不是优化带权路径。 · 希望避免递归深度限制。
- Invariant
- 队列中的节点已被发现并归属当前分量，但尚未展开；未访问节点尚未被证明从当前起点可达。
- 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
Free网格 Flood Fill
- Recognition
- 输入是 grid、image 或 board，移动到相邻格。 · 题意出现岛屿、区域、颜色、洞或边界。
- Invariant
- frontier 中每个坐标都已通过边界和谓词检查并被标记；弹出后只需扩展合法邻居。
- 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
Free拓扑排序 / 入度消除
- Recognition
- 出现 prerequisite、dependency、build order。 · 要求满足所有先后约束的排列。
- Invariant
- frontier 中节点在当前剩余图中入度为零；输出 u 后只有 u 的直接后继入度减少。
- 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
接下来的 families
Pro only有序前沿与路径
Pro only二分与单调答案
Pro only双指针与滑动窗口
Pro only前缀、差分与哈希状态
Pro only栈、单调栈与单调队列
Pro only堆、选择与流
Pro only贪心与调度
Pro only分治与归并计数
Pro only动态规划
Pro only回溯与约束搜索
Pro only树、BST 与 Trie
Pro only并查集、MST 与离线激活
Pro only区间查询数据结构
Pro only字符串匹配、哈希与回文
Pro only数学、数论与组合
Pro only位运算与位掩码状态
Pro only几何、扫描线、模拟与解析