给定一个有向图，检测其中是否存在环。请给出两种不同的解法。

Given a directed graph, detect if it contains a cycle. Provide two different approaches.

题目类型: 技术面试题

这是一道技术面试题，常见于澳洲IT公司面试中。

难度: hard

标签: dropbox, generated

目标公司: Dropbox

参考答案摘要

思路分析 方法1: DFS + 三色标记（白/灰/黑）。方法2: 拓扑排序（Kahn's BFS），若无法完成则有环。 参考答案 DFS: 维护 visiting（灰色）集合，遇到灰色节点则有环。拓扑排序: 入度为0的节点入队，处理完后若还有未访问节点则有环。 评分要点 两种方法的正确实现 时间空间复杂度分析 理解两种方法的适用场景 常见追问 如何输出环的具体路径？ 在Dropbox的依赖管理中如...

本题提供 STAR 原则详细解答和技术解析，登录匠人学院学习中心即可查看完整答案。