Amazon VO 面试真题解析：判断无向图是否有环

Determine if an undirected graph has cycle.

Example 1:

[[1,2],[1,3],[2,3]] -> return true

Example 2:

[[1,2],[2,3],[3,4],[1,5]] -> return false

这道题要求判断一个无向图中是否存在环。常见做法是先把边列表转换成邻接表，然后用 DFS 或并查集来检测是否出现“已经访问过但不是父节点”的回边；如果是并查集，则在合并每条边时检查两个端点是否已经属于同一个集合。题目示例中，[[1,2],[1,3],[2,3]] 会形成三角形，因此返回 true；而 [[1,2],[2,3],[3,4],[1,5]] 是一棵树加一个独立连接，不存在环，返回 false。