题目描述

给定一组元素，及其依赖关系，一个元素可以依赖于多个元素(不包括自己，被依赖元素不会重复)一个元素也可被多个元素依赖。假定总是存在唯一的循环依赖，请输出该循环依赖。

题面描述:

给定一组元素及其依赖关系，其中一个元素可以依赖多个其他元素，且一个元素也可以被多个其他元素所依赖。在输入中，首先给出依赖关系的数量，接着每行描述一个元素及其依赖的元素。任务是输出唯一存在的循环依赖，从最小的元素编号开始，依次输出依赖关系，最后以该最小元素结束。通过分析依赖关系，可以确定循环依赖的路径。

思路

简化题意：给出若干条边组成的有向图，找出其中唯一的环，保证环一定存在。 直接 dfs ，遍历完点 u 还未找到环，则说明点 u 不在这个环上。 当某个点已经被遍历过一次，且在 dfs 过程中再次被遍历过，说明遍历完了一整个环。 具体实现上使用一个栈来存储 dfs 过程中遍历到的点，如果一个点 u 被遍历到了两次，则说明找到了这个环，且 u 是这个环上的点。 只需要依次弹出栈中的点，直至弹出 u 为止，这就是环中所有的点。