C++ :: Depth-First Search Algorithm (DFS)

.:: PSEUDOCODE ::.

---

DFS(G)
    for each vertex u ∈ G.V
        u.color = WHITE
        u.π = NIL
    time = 0
    for each vertex u ∈ G.V
        if u.color == WHITE
            DFS-VISIT(G,u)

DFS-VISIT(G,u)
    time = time + 1
    u.d = time
    u.color = GRAY
    for each v ∈ G.Adj[u]
        if v.color == WHITE
            v.π = u
            DFS-VISIT(G,v)
    u.color = BLACK
    time = time + 1
    u.f = time

.:: C++ Code ::.

---

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <limits>
#define MAX 101
using namespace std;

enum colors {BLACK, WHITE, GRAY};
int color[MAX], d[MAX], p[MAX], f[MAX], t, vertex, edge;
int NIL = numeric_limits<int>::min();

void DFS(vector<int>[]);
void DFS_VISIT(vector<int>[],int);

int main(void)
{
    //freopen("dfs.txt", "r", stdin);
    vector<int> adjList[MAX];
    int u, v;
    cin >> vertex >> edge;
    for(int e=1; e<=edge; e++) {
        cin >> u >> v;
        adjList[u].push_back(v);
    }
    DFS(adjList);
    for(int v=1; v<=vertex; v++) {
        printf("v%d (%d/%d)\n", v, d[v], f[v]);
    }
    return 0;
}

void DFS(vector<int> G[]) {
    for(int u=0; u<=vertex; u++) {
        color[u] = WHITE;
        p[u] = NIL;
    }
    t = 0;
    for(int u=1; u<=vertex; u++) {
        if(color[u] == WHITE) {
            DFS_VISIT(G,u);
        }
    }
}

void DFS_VISIT(vector<int> G[], int u) {
    t = t + 1;
    d[u] = t;
    color[u] = GRAY;
    for(int v=0; v<G[u].size(); v++) {
        if(color[G[u][v]] == WHITE) {
            p[G[u][v]] = u;
            DFS_VISIT(G,G[u][v]);
        }
    }
    color[u] = BLACK;
    t = t + 1;
    f[u] = t;
}

.:: Sample Input ::.

---

6 8
1 2
1 4
2 5
3 5
3 6
4 2
5 4
6 6

.:: Sample Output ::.

---

v1 (1/8)
v2 (2/7)
v3 (9/12)
v4 (4/5)
v5 (3/6)
v6 (10/11)

.:: DFS Related UVa Problems ::.

---

• 129 - Krypton Factor
• 310 - L-System
• 707 - Robbery
• 782 – Contour Painting
• 784 – Maze Exploration
• 10103 - Karpovich Blocks
• 10113 - Exchange Rates
• 10276 - Hanoi Tower Troubles Again
• 10452 - Marcus Help!
• 10728 - Help!
• 11244 – Counting Stars
• 11283 - Playing Boggle
• 11470 – Square Sums
• 11504 – Dominos
• 11518 - Dominos 2

Refference: Introduction to Algorithms - Thomas H. Cormen