知识点指南

Graphs

Graphs model connections. Nodes represent objects or states, and edges represent roads, relationships, moves, or dependencies.

什么时候使用

读题时可以留意这些信号。

The problem talks about roads, bridges, paths, reachability, components, or moves.
You need to know what can be reached from a starting point.
The state can be represented as nodes and transitions.

常见错误

提交前可以检查这些小陷阱。

Treating directed edges as undirected.
Marking visited too late.
Forgetting disconnected components.

怎么写成代码

把知识点翻译成变量、循环、判断和更新。

Build an adjacency list from input edges.
Use BFS/DFS to visit reachable nodes.
Mark nodes visited as soon as they are discovered.
For components, start a new traversal from each unvisited node.

在 Block 题里长什么样

答题时通常会看到这些步骤被拆成代码块。

1Read N and M.
2Create adjacency list.
3Add each edge, respecting direction.
4Initialise visited and queue/stack.
5Traverse graph.
6Output reachability/count/distance.

题目里怎么出现

读题时先找这些信号，再决定答案区应该选哪些 blocks。

The story has locations and connections.
The answer depends on whether travel/communication is possible.
A direct list scan is not enough because connections chain together.

BFS reachability

一个小型模板，展示代码和 blocks 的对应关系。

C++

queue<int> q;
visited[start] = true;
q.push(start);
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : adj[u]) {
        if (!visited[v]) {
            visited[v] = true;
            q.push(v);
        }
    }
}

Python

from collections import deque
q = deque([start])
visited[start] = True
while q:
    u = q.popleft()
    for v in adj[u]:
        if not visited[v]:
            visited[v] = True
            q.append(v)

对应 block 顺序

1Build adjacency list.
2Create visited array.
3Push start node.
4While queue is not empty, pop node.
5Loop over neighbours.
6Visit unseen neighbours.