题解：P6911 [ICPC2015 WF] Qanat

Qinglan2011 · 2024-08-23 15:45:48 · 题解

其实这道题题意很好理解，但是思考和代码实现很难。

我们将地形图给抽象一下，转化成无向图，特殊的位置用节点表示，如果有修建 qanat 的通道，那么就会形成一条边。

这样的话，我们就可以用深搜或广搜遍历图，同时做一个标记。通过标记，可以比较快速地判断任意两个节点是否在同一连通分量内，也就是说它们是否可通过 qanat 相连。

完成以上操作后，我们就会发现查询变得轻松多了。现在，我们只需对比一下标记。如果是一样的，那么它们属于一个 qanat 系统，可以连通；如果不是，则反之。