《挑战程序设计竞赛》笔记
探索图算法的核心：关节点与树的直径
在程序设计竞赛中，图算法始终是考察选手算法功底的重要领域。《挑战程序设计竞赛》一书中，作者渡部有隆以其独特的视角和深入浅出的风格，为读者揭示了图算法的精妙之处。本文将重点探讨书中关于关节点和树的直径的内容，结合实例和代码，深入分析这些算法的核心思想及其应用。
关节点的筛选：DFS算法的艺术
关节点（Articulation Point）是图论中的一个重要概念，它指的是图中若移去该顶点及其所有与其相连的边，图的连通分量数目会增加的顶点。作者通过DFS算法巧妙地解决了关节点的筛选问题。
在DFS遍历过程中，作者引入了两个关键数组：prenum[u]和lowest[u]。prenum[u]记录顶点u的DFS预序编号，而lowest[u]则记录顶点u的最低后序编号。通过这些信息，我们可以判断某个顶点是否为关节点。
具体来说，关节点的筛选规则如下：
1. 如果树T的根结点r拥有两个或以上的子结点，则r为关节点。
2. 对于某个顶点u，设其父结点为p，如果prenum[p] ≤ lowest[u]，则p为关节点。
作者通过图15.1和图15.2的实例，生动地展示了这些规则的应用。例如，在图15.1中，顶点3满足prenum[3] ≤ lowest[5]，因此顶点3被识别为关节点。
以下是实现关节点筛选的代码框架：
void dfs(int current， int prev)
prenum[current] = lowest[current] = timer++;
visited[current] = true;
for (int next : G[current])
if (!visited[next])
parent[next] = current;
dfs(next， current);
lowest[current] = min(lowest[current]， lowest[next]);
else if (next != prev)
lowest[current] = min(lowest[current]， prenum[next]);
void art_points()
timer = 1;
dfs(0， -1);
set<int> ap;
int np = 0;
for (int i = 1; i < N; i++)
int p = parent[i];
if (p == 0) np++;
else if (prenum[p] <= lowest[i]) ap.insert(p);
if (np > 1) ap.insert(0);
for (int node : ap)
cout << node << endl;
树的直径：最远距离的计算
树的直径是指树中两个最远结点之间的距离。作者提出了一种高效的算法来计算树的直径，其核心思想可以分为以下三个步骤：
1. 任选一个结点s，找到到s最远的结点x。
2. 从结点x出发，找到到x最远的结点y。
3. 结点x与结点y之间的距离即为树的直径。
这种算法的正确性可以通过以下几点来验证：
– 树的性质确保了任意两结点之间只有一条唯一的路径。
– 算法的第一步和第二步实际上已经覆盖了所有可能的最远路径情况。
例如，在输入示例1中，树的结构如下：
输入示例1：
4
0 1 2
1 2 1
2 3 3
通过算法计算，树的直径为2 + 1 + 3 = 6，即结点0到结点3的距离。
以下是计算树的直径的代码实现：
void bfs(int start， vector<int>& d)
queue<int> q;
d[start] = 0;
q.push(start);
while (!q.empty())
int u = q.front();
q.pop();
for (Edge e : G[u])
if (d[e.t] == INFTY)
d[e.t] = d[u] + e.w;
q.push(e.t);
int main()
cin >> n;
for (int i = 0; i < n - 1; i++)
int s， t， w;
cin >> s >> t >> w;
G[s].emplace_back(t， w);
G[t].emplace_back(s， w);
vector<int> d1(n， INFTY);
bfs(0， d1);
int x = max_element(d1.begin()， d1.end()) - d1.begin();
vector<int> d2(n， INFTY);
bfs(x， d2);
int diameter = max(d2.begin()， d2.end());
cout << diameter << endl;
return 0;
算法的意义与应用
关节点和树的直径的计算不仅是图论中的经典问题，也在实际应用中具有重要意义。例如，关节点的识别可以用于网络的可靠性分析，而树的直径则可以用于路由协议的优化。
通过本书的学习，我们不仅掌握了这些算法的实现细节，更深刻理解了图论在实际问题中的应用价值。作者用生动的语言和清晰的思路，为读者打开了图算法的大门。
这篇笔记仅是对书中内容的简要概括和思考，感兴趣的读者可以进一步深入研究。