dfs_bfs_good.cpp

/*
 * =====================================================================================
 *
 *       Filename:  graph_traversals.cpp
 *
 *    Description:  
 *
 *        Version:  1.0
 *        Created:  06/03/2015 02:55:12 PM
 *       Revision:  none
 *       Compiler:  gcc/g++
 *
 *         Author:  Marius-Constantin Melemciuc  
 *          email:  
 *   Organization:  
 *
 * =====================================================================================
 */

#include <iostream>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

vector<bool> visited;

vector<vector<int> > graph;

void dfs(int vertex) {
    stack<int> s;
    s.push(vertex);
    visited[vertex] = true;

    while (!s.empty()) {
        int element = s.top();
        int count = graph[element].size();
        int i;
        bool found = false;
                
        for (i = 0; i < count && !found; i++) 
            if (!visited[graph[element][i]])
                found = true;

        if (found) {
            i--;
            s.push(graph[element][i]);
            visited[graph[element][i]] = true;
        } else {
            s.pop();
        }
    }
}

void bfs(int vertex) {
    queue<int> q;
    q.push(vertex);
    visited[vertex] = true;

    while (!q.empty()) {
        int element = q.front();
        int count = graph[element].size();

        for (int i = 0; i < count; i++) 
            if (!visited[graph[element][i]]) {
                q.push(graph[element][i]);
                visited[graph[element][i]] = true;
            }

        q.pop();
    }
}

int main() {
    int n, m;

    cin >> n >> m;

    vector<int> row;
    for (int i = 0; i <= n; i++)
        graph.push_back(row);

    for (int i = 0; i < m; i++) {
       int x, y;

       cin >> x >> y;
       graph[x].push_back(y);
       graph[y].push_back(x); 
    }

    for (int i = 0; i <= n; i++)
        visited.push_back(false);

    dfs(1);

    return 0;
}