## 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: 8 years ago
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 i

def __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: 8 years ago
Location: Cuba
Gender:

### Re: DFS

Here an example of DFS in Ruby:

Code: Select all

``````def DFS(graph, pos)
marks = [false] * graph.size
marks[pos] = true
__DFS(graph, pos, marks){ |i| yield i }
end

def __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
end
end

#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: 8 years ago
Gender:

### Re: DFS

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