给定一组元素及其依赖关系,其中一个元素可以依赖多个其他元素,且一个元素也可以被多个其他元素所依赖。在输入中,首先给出依赖关系的数量,接着每行描述一个元素及其依赖的元素。任务是输出唯一存在的循环依赖,从最小的元素编号开始,依次输出依赖关系,最后以该最小元素结束。通过分析依赖关系,可以确定循环依赖的路径。
简化题意:给出若干条边组成的有向图,找出其中唯一的环,保证环一定存在。 直接 dfs ,遍历完点 u 还未找到环,则说明点 u 不在这个环上。 当某个点已经被遍历过一次,且在 dfs 过程中再次被遍历过,说明遍历完了一整个环。 具体实现上使用一个栈来存储 dfs 过程中遍历到的点,如果一个点 u 被遍历到了两次,则说明找到了这个环,且 u 是这个环上的点。 只需要依次弹出栈中的点,直至弹出 u 为止,这就是环中所有的点。
给定一组元素,及其依赖关系,一个元素可以依赖于多个元素(不包括自己,被依赖元素不会重复)一个元素也可被多个元素依赖。假定总是存在唯一的循环依赖,请输出该循环依赖。
第一行一个正整数N,表示依赖关系的个数。
接下来每一行表示一个依赖关系,是由空格分割的多个正整数,第一个数n表示后面有n个元素,第二个数为元素编号a,后面多个数为a依赖的元素编号,任意元素i满足0<t<10000
一串数字,代表这个循环依赖,从最小元素编号开始,按照依赖关系依次输出,以最小元素结束。
输入
3
3 1 2 5
3 2 3 4
2 3 1
输出
1 2 3 1
说明