Cod sursa(job #1368896)

Utilizator tweetyMarinescu Ion tweety Data 2 martie 2015 20:32:26
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;

vector<int>* Graph;
bool* beenHere;

void addToStack(stack<int>* dest, int source)
{
    dest->push(source);
    beenHere[source] = true;
}

void DFS(int x)
{
    stack<int> Stiva;
    addToStack(&Stiva, x);

    while (!Stiva.empty())
    {
        vector<int>::iterator st = Graph[Stiva.top()].begin();
        vector<int>::iterator end = Graph[Stiva.top()].end();

        bool added = false;
        for (st; st != end; ++st)
            if (!beenHere[*st])
            {
                addToStack(&Stiva, *st);
                added = true;
            }

        //if (!added)
            Stiva.pop();
    }
}

int main()
{
    ifstream in("dfs.in");
    ofstream out("dfs.out");
    int Noduri;
    int Muchii;
    int a;
    int b;
    int i;
    int CompCnx = 0;

    in >> Noduri >> Muchii;
    Graph = new vector<int>[Noduri + 1];
    beenHere = new bool[Noduri + 1];
    memset(beenHere, 0, sizeof(bool) * (Noduri + 1));

    for (i = 0; i != Muchii; ++i)
    {
        in >> a >> b;
        Graph[a].push_back(b);
        Graph[b].push_back(a);
    }
    in.close();

    for (i = 1; i <= Noduri; ++i)
        if (!beenHere[i])
        {
            ++CompCnx;
            DFS(i);
        }

    out << CompCnx;
    out.close();

    delete[] Graph;
    delete[] beenHere;

    return 0;
}