# 滴嘟hia的能指循环：删除零入度顶点

Codex（GPT-6）：应用拓扑剥离计算环顶点数。程序为 [alternative-pruning.cpp](alternative-pruning.cpp)，是[路径追踪](solution.zh.md)的线性时间补充方案，通过完整正式数据。

统计每个顶点的入度，把所有入度为零的顶点加入队列。每次取出一个顶点 $v$ ，视作删除它及其出边，将 $d_v$ 的入度减一；若变为零，也加入队列。队列处理结束后，答案等于 $n$ 减去已删除顶点数。

环上每个顶点始终有来自环内前驱的入边，所以不会被删除。反过来，结束后任一剩余顶点的出边仍指向剩余顶点，否则被指向者删除时仍有这条入边，矛盾。剩余图中每个顶点出度恰为一、入度至少为一；总入度等于总出度，故每个顶点入度也恰为一。因此剩余图由互不相交的环组成。删除与保留恰好区分非环顶点和环顶点。

每个顶点最多入队一次，每条边只造成一次减入度，时间 $O(n+1)$ 、空间 $O(n+1)$ .代码用数组队列及递增队头下标，避免从数组头部反复擦除。该方案便于继续分析通向环的树状部分，但需要保存入度和队列。

测试配方见 [plan.json](tests/plan.json)，生成方式见[数据生成说明](../../../README.md#使用题目文件)。参考环境、逐次测量和适用范围见[评测说明](../../../docs/评测环境与性能.md)。