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有序前沿与路径
Only available for Pro members
Pro only二分与单调答案
Only available for Pro members
Pro only双指针与滑动窗口
Only available for Pro members
Pro only前缀、差分与哈希状态
Only available for Pro members
Pro only栈、单调栈与单调队列
Only available for Pro members
Pro only堆、选择与流
Only available for Pro members
Pro only贪心与调度
Only available for Pro members
Pro only分治与归并计数
Only available for Pro members
Pro only动态规划
Only available for Pro members
Pro only回溯与约束搜索
Only available for Pro members
Pro only树、BST 与 Trie
Only available for Pro members
Pro only并查集、MST 与离线激活
Only available for Pro members
Pro only区间查询数据结构
Only available for Pro members
Pro only字符串匹配、哈希与回文
Only available for Pro members
Pro only数学、数论与组合
Only available for Pro members
Pro only位运算与位掩码状态
Only available for Pro members
Pro only几何、扫描线、模拟与解析
Only available for Pro members