如题,设正向图中每个节点的出度为 outord,类似“拓扑排序”的思想,可以在从 t 点出发,广度优先搜索反向图的过程中,在搜索未访问过的相邻节点的同时,把每个相邻节点的出度减一。这样反向图搜索完成后,在反向图中,所有可以从 t 点出发访问到,且 outord 为 0 的节点,都是符合题目要求的节点。从 t 点出发,再次遍历反向图即可求出答案。该方案相比“遍历反向图 →\to→ 求可用节点 →\to→ 再次遍历正向或反向图”的方案大约减少 1/3 的图边访问量,预计可提速 ×1.5\times 1.5×1.5。
outord
t