C++ - Zadatak Graf - rjesenje

/*

Pripreme 2013 - C++ radionica

TEMA : Obilazak grafa (najkraci putevi izmedju dva cvora)

Zadatak: Graf

Autor zadatka: Kristijan Burnik

Autor rjesenja: Kristijan Burnik

Datum rjesavanja: 2013-01-08

*/
#include <iostream>
#include <cstdlib>
#include <vector>
#include <map>
#include <set>

using namespace std;

// koliko je najdulja putanja?
const int MAX_PATH_LENGTH = 1000;

typedef string node;
typedef vector< node > nodelist;
typedef set< node > nodeset;
typedef map< node,bool >::iterator IT;


// struktura za pohranu grafa (korisna za listu susjeda od nekog cvora)
map <node, map< node,bool> > graph;

// putanja do cvora
nodelist path;

// popis vidjenih cvorova
set <node> seen;

// minimalna izracunata duljina putanje
int minPathLength = MAX_PATH_LENGTH;

// popis svih putanja (rezultati pretrage)
// rezultate puni DFS
vector < nodelist > results;

// pomocna procedura za prikaz pojedinog rezultata (jedne putanje)
void display( nodelist v ) {
    cout << v[0];
    for (int i = 1; i < v.size(); i++) {
        cout << " -> " << v[i];
    }
    cout << endl;
}

// obilazak grafa
// ( koristimo reference za ustedu vremena kopiranja i funkcijskog stoga )
void traverse( node current , node end ) {

    // postavi trenutni cvor u listu (putanju)
    path.push_back( current );

    // oznaci da je trenutni cvor vidjen
    seen.insert( current );

    // provjeri jesmo li dosli do odredisnog cvora
    if (current == end) {
        // ako je izracunata putanja manja, isprazni rezultate
        if ( path.size() < minPathLength ) {
            minPathLength = path.size();
            results.clear();
        }
        // puni rezultate samo za jednake duljine putanje
        if ( path.size() == minPathLength) {
            results.push_back( path );
        }

    } else {
        // uzmi susjede od zadanog cvora
        map<node,bool> adjacents = graph[ current ];

        // prodji sve susjedne cvorove od trenutnog
        for (IT it = adjacents.begin(); it != adjacents.end(); it++ ) {
            node nextnode = it->first;
            // samo jos nevidjene cvorove obradjujemo
            if (!seen.count(nextnode)) {

                // oznaci da je cvor vidjen
                seen.insert( nextnode );

                // nastavi obilazak na iducem cvoru,
                // proslijedi trenutnu putanju i popis vidjenih
                traverse( nextnode , end );

                // makni iz popisa vidjenih
                seen.erase( nextnode );
            }
        }
    }

    // makni trenutni cvor sa putanje
    path.pop_back();

    // makni trenutni cvor iz popisa vidjenih
    seen.erase( current );

}

// procedura za pripremu i poziv obilaska (traverse)
void findpaths( node a, node b ) {
    // ocisti rezultate pretrage
    results.clear();

    // postavi minimalnu putanju na maksimalnu mogucu
    minPathLength = MAX_PATH_LENGTH;

    // isprazni putanju i popis vidjenih
    nodelist path;
    nodeset seen;

    // pozovi dfs za pretragu putanje a -> ... -> b
    // sa praznom putanjom i praznim skupom vidjenih cvorova
    traverse( a , b );
}

int main() {
    int n ,k;

    // koliko imamo bridova?
    cin >> n;

    // unesi i konstruiraj graf
    node a,b;
    for (int i = 0 ; i < n; i++) {
        cin >> a >> b;
        graph[a][b] = graph[b][a] = true;
    }

    // koliko imamo upita za pretragu?
    cin >> k;

    // obradi sve upite
    for (int i = 0; i < k; i++) {

        // unesi par cvorova (ciju putanju trazimo ?)
        cin >> a >> b;

        // pronadji sve najkrace puteve
        // rezulti spremljeni globalno u "results"
        findpaths(a,b);

        // ako nema rezultata ispisi da nema puta
        if (results.size() > 0) {
            // ispisi sve rezultate koje je generirao DFS
            for (int i = 0 ; i < results.size(); i++)  {
                display( results[i] );
            }
        } else {
            cout << "Nema puta" << endl ;
        }

    }

    system("pause");
    return 0;
}