summaryrefslogtreecommitdiff
path: root/cpp/dfs.cc
diff options
context:
space:
mode:
Diffstat (limited to 'cpp/dfs.cc')
-rw-r--r--cpp/dfs.cc65
1 files changed, 65 insertions, 0 deletions
diff --git a/cpp/dfs.cc b/cpp/dfs.cc
new file mode 100644
index 0000000..bb0bd22
--- /dev/null
+++ b/cpp/dfs.cc
@@ -0,0 +1,65 @@
+#include <iostream>
+#include <list>
+
+#define WHITE 0
+#define GREY 1
+#define BLACK 2
+#define INF 99999
+
+using namespace std;
+
+int checked[INF] = {WHITE};
+int d[INF] = {0};
+int f[INF] = {0};
+int t = 1;
+
+void dfs(list<int> lista[], int start) {
+ checked[start] = GREY;
+ d[start] = t++;
+
+ for(auto it = lista[start].begin(); it != lista[start].end(); it++) {
+ if(checked[*it] == WHITE)
+ dfs(lista, *it);
+ }
+
+ checked[start] = BLACK;
+ f[start] = t++;
+
+ cout << start << '(' << d[start] << ',';
+ cout << f[start] << ')' << endl;
+}
+
+int main() {
+ int u, w;
+ int e;
+ cin >> e;
+ list<int> lista[INF];
+ for(int i = 0; i < e; ++i) {
+ cin >> u >> w;
+ lista[u].push_back(w);
+ }
+
+ dfs(lista, 0); //0 is the start
+
+ /* example:
+ http://pages.cs.wisc.edu/~mcw/cs367/lectures/images/dfs.gif
+ #input
+ 8
+ 0 1
+ 0 5
+ 1 2
+ 2 0
+ 1 3
+ 3 4
+ 4 2
+ 1 4
+ #output
+ 2(3,4)
+ 4(6,7)
+ 3(5,8)
+ 1(2,9)
+ 5(10,11)
+ 0(1,12)
+ */
+ return 0;
+}