hiho一下第215周《Circle Detect》题目分析

6
1

《Circle Detect》题目分析

这道题是一道经典图论题,判断有向图中是否有环。

比较常用的做法是DFS,同时在DFS过程中对点染色:

  1. 还没被DFS访问的点是白色的,初始时所有点都是白色的
  2. 如果点u已经被DFS访问过,但是u的子节点还未全部被访问到,那么把u染成灰色
  3. 如果点u以及u的子节点都被访问过了,从u回溯到u的父节点时,将u染成黑色

如果在DFS的过程中我们沿着有向边到达了一个灰色节点,则说明图中有环;如果从未到达过灰色节点,说明没有环。

伪代码如下:

DFS(x):
    color[x] = GREY
    FOR y : g[x] # x->y是一条边
        IF color[y] == GREY
            EXIT(CIRCLE_FOUND)
        IF color[y] == WHITE
            DFS(y)
    color[x] = BLACK
MAIN:
    FOR x = 1 .. N:
        IF color[x] == WHITE:
            DFS(x)
    EXIT(CIRCLE_NOT_FOUND)

1 answer(s)

1

这个问题用递归不会栈溢出吗?

  • hihoCoder评测机是ubuntu的,栈空间已经调的比内存限制还大了。自己本地测试可能得自己调一下。

  • 添加评论
  • reply

write answer 切换为英文 切换为中文


转发分享