Codeforces #357 D. Gifts by the List

正文索引 [隐藏]

传送门:http://codeforces.com/contest/681/problem/D

题目大意

首先输入 n , m ,表示有 n 个人, m 对父子关系。
接下来的 m 行,输入 m 对父子关系,每对 x , y 表示 x 是 y 的父亲。
接下来一行的 n 个数,表示编号为 n 的人想要送礼物的目标标号。
我们需要构造一个 List ,是的每一个人顺着 List ,从前往后找到的第一个自己的祖先就是自己想要送礼物的目标。
题目保证,每个人送礼目标只会是自己/自己的祖先。

题解

DFS 我们考虑每个人,他的送礼物目标不可能与他的父亲的目标交叉,所以每个人送礼物的目标只可能是自己/自己的父亲/自己父亲的送礼物目标。如果不是,则无解输出 -1 ,否则礼物目标进栈,最后输出方案只需要把栈弹完即可。

代码