## DFS

Discussion around the algorithms: the most powerful tool of the contest programmer. This is the place to ask about the algorithms you have heard mention, or to share with the community your knowledge about them.
Forum rules
Remember that you may not post the AC solution to any of the problems on the COJ. Only code pertaining to a general algorithm will be allowed.
Posting AC solutions will be penalized.
Phantom
Posts: 58
Joined: Thu Nov 17, 2011 11:21 am
Location: Cuba
Gender:

### DFS

Here an example of DFS in Python:

Code: Select all

`def DFS(graph, pos):    marks = [False] * len(graph)    marks[pos] = True    for i in __DFS(graph, pos, marks):yield idef __DFS(graph, pos, marks):    for i in graph[pos]:        if not marks[i]:            marks[i] = True            yield i            for j in __DFS(graph, i, marks):yield j#Example:           graph = [[3], [0, 2, 5], [3, 4], [1, 0], [5, 3], [0, 1, 2, 3]]for i in DFS(graph, 1): print i`

Phantom
Posts: 58
Joined: Thu Nov 17, 2011 11:21 am
Location: Cuba
Gender:

### Re: DFS

Here an example of DFS in Ruby:

Code: Select all

`def DFS(graph, pos)marks = [false] * graph.sizemarks[pos] = true__DFS(graph, pos, marks){ |i| yield i }enddef __DFS(graph, pos, marks)   for i in graph[pos]:     if !marks[i]        marks[i] = true        yield i        __DFS(graph, i, marks){ |j| yield j }     end   endend#Example:graph = [[3], [0, 2, 5], [3, 4], [1, 0], [5, 3], [0, 1, 2, 3]]DFS(graph, 1){ |i| puts i }`

Spartan
Posts: 11
Joined: Thu Apr 05, 2012 9:36 pm
Gender:

### Re: DFS

someone could write an efficient code on c++? i just want to know 2 or 3 differents ways to do it.