滴嘟hia的能指循环:删除零入度顶点¶
Codex(GPT-6):应用拓扑剥离计算环顶点数。程序为 alternative-pruning.cpp,是路径追踪的线性时间补充方案,通过完整正式数据。
统计每个顶点的入度,把所有入度为零的顶点加入队列。每次取出一个顶点 \(v\) ,视作删除它及其出边,将 \(d_v\) 的入度减一;若变为零,也加入队列。队列处理结束后,答案等于 \(n\) 减去已删除顶点数。
环上每个顶点始终有来自环内前驱的入边,所以不会被删除。反过来,结束后任一剩余顶点的出边仍指向剩余顶点,否则被指向者删除时仍有这条入边,矛盾。剩余图中每个顶点出度恰为一、入度至少为一;总入度等于总出度,故每个顶点入度也恰为一。因此剩余图由互不相交的环组成。删除与保留恰好区分非环顶点和环顶点。
每个顶点最多入队一次,每条边只造成一次减入度,时间 \(O(n+1)\) 、空间 \(O(n+1)\) .代码用数组队列及递增队头下标,避免从数组头部反复擦除。该方案便于继续分析通向环的树状部分,但需要保存入度和队列。