题解:P5053 [COCI 2017/2018 #7] Clickbait

· · 题解

晓声明

如题解描述有雷同,纯属巧合,请各位 dalao 谅解。

体面大意

有一个由容器和管道组成的排水系统,对于这个系统, 想知道如果向第一个容器灌水,所有容器从空的状态到装满水的状态的顺序。

解题思路

此题可以看作一个平面图,而我们要做的就是遍历整个图,求顺序。既然要求顺序,我们就又可以想到深搜和广搜,由于这是属于求路径类型的题目,所以建议选择深搜。

解题步骤

先暴力搜到第一个箱子

从头向尾开始深搜,由于深搜是一条路走到黑,所以可以将管子看作一条条的通道,如果这个地方有通道连向其他地方,就延着这条路继续往黑走。

重复向尾搜索,直到此刻没有路了(一条路走黑了)就输出这个地方的编号,结束搜索。