Cod sursa(job #1464262)

Utilizator linerunnerMihai Ion linerunner Data 22 iulie 2015 19:56:20
Problema Parcurgere DFS - componente conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.59 kb
#include <iostream>
#include <fstream>
#include <list>
#include <stack>
#include <vector>
#define MAX 200001

using namespace std;

typedef struct
{
    int indice;
    char culoare = 'N';
}   nod;

void DFS(nod *nodgraf, list <nod> *graf)
{
    stack <nod> stiva;
    nodgraf->culoare = 'V';
    stiva.push(*nodgraf);
    while ( !stiva.empty() )
    {
        nod nodTop = stiva.top();
        int vecin = -1;
        std::list<nod>::iterator it;
        for ( it = graf[nodTop.indice].begin() ; it != graf[nodTop.indice].end() ; ++it )
            if ( it->culoare == 'N' )
            {
                vecin = it->indice;
                it->culoare = 'V';
                stiva.push(*it);
                break;
            }


        if ( vecin == -1 )
            stiva.pop();
    }
}

int Complet(list <nod> *graf, int NrNoduri)
{
    int i;
    for ( i = 1 ; i <= NrNoduri ; i++ )
    {
        std::list<nod>::iterator it;
        for ( it = graf[i].begin() ; it != graf[i].end() ; ++it )
            if ( it->culoare == 'N' )
                return 0;
    }

    return 1;

}

int CautaNodNeparcurs(list <nod> *graf, int NrNoduri)
{
    int i;
    for ( i = 1 ; i <= NrNoduri ; i++ )
    {
        std::list<nod>::iterator it;
        for ( it = graf[i].begin() ; it != graf[i].end() ; ++it )
            if ( it->culoare == 'N' )
                return i;
    }

    return 1;
}

int ComponenteConexe(list <nod> *graf, int NrNoduri)
{
    int compconexe = 0;
    while ( !Complet(graf, NrNoduri) )
    {
        int n = CautaNodNeparcurs(graf, NrNoduri);
        nod n1;
        n1.indice = n;
        DFS(&n1, graf);
        compconexe++;
    }

    return compconexe;
}

int main()
{
    ifstream input("dfs.in");
    ofstream output("dfs.out");

    int NrNoduri, NrMuchii, i;

    /* Citire Date */
    input >> NrNoduri >> NrMuchii ;

    list <nod> graf[MAX];
    nod nod1, nod2;

    for ( i = 0 ; i < NrMuchii ; i++ )
    {
        input >> nod1.indice >> nod2.indice;
        graf[nod1.indice].push_back(nod2);
        graf[nod2.indice].push_back(nod1);
    }

    int cc = 0;

    /* Afisare Graf */
    for ( i = 1 ; i <= NrNoduri ; i++ )
    {
 /*
        output << i ;
        std::list<nod>::iterator it;
        for ( it = graf[i].begin() ; it != graf[i].end() ; ++it )
            output << "->" << it->indice << "," << it->culoare;
        output << "\n";
*/
        if ( graf[i].empty() )
            cc++;
    }

    cc = cc + ComponenteConexe(graf, NrNoduri);
    output << cc ;


    return 0;
}