Cod sursa(job #741359)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 25 aprilie 2012 21:35:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb

#include <fstream>
#include <list>
#include <vector>

typedef std::list<unsigned int> adiacent;
typedef std::vector<adiacent> nod;

nod graf;
bool *mark;

void DepthFirstSearch (unsigned int nod)
{
    mark[nod] = true;
    adiacent::iterator stop(graf[nod].end());
    for (adiacent::iterator i(graf[nod].begin()) ; i != stop ; ++i)
    {
        if (!mark[*i])
            DepthFirstSearch(*i);
    }
    graf[nod].clear();
}

int main (void)
{
    unsigned int n,m;
    std::ifstream input("dfs.in");
    input >> n >> m;
    graf.resize(n + 1);    
    unsigned int x,y;
    while (m)
    {
        input >> x >> y;
        graf[x].push_front(y);
        graf[y].push_front(x);
        --m;
    }
    input.close();
    unsigned int counter(0);
    mark = new bool [n + 1] ( );
    for (unsigned int index(1) ; index <= n ; ++index)
    {
        if (!mark[index])
        {
            ++counter;
            DepthFirstSearch(index);
        }
    }
    delete [ ] mark;
    std::ofstream output("dfs.out");
    output << counter << '\n';
    output.close();
    return 0;
}