Cod sursa(job #536209)

Utilizator nahsucpasat cristian nahsuc Data 18 februarie 2011 13:20:46
Problema Parcurgere DFS - componente conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
/*
                    FACUTA CU
        PARCURGEREA BREADTH FIRST SEARCH
*/
#include<stdio.h>
#include<vector>
#include<list>
#define nodmax 100001
using namespace std;
FILE *in,*out;
vector < list<int> > matrix(nodmax);
vector < int > vizitat(nodmax);
vector < int > coada;

int varfuri,muchii,startNode,cont;

void read();
void BFS(int startNode);
void print();


int main()
{
    int i;
    read();
    for(i=1;i<=varfuri;i++)
    {
        if(!vizitat[i])
            BFS(i);
    }

    print();
    return 0;
}

void read()
{
    int i,x,y;
    in=fopen("dfs.in","rt");
    fscanf(in,"%d%d",&varfuri,&muchii);
    for(i=1;i<=muchii;i++)
       {
            fscanf(in,"%d%d",&x,&y);
            matrix.at(y).push_back(x);
            matrix.at(x).push_back(y);
       }
    fclose(in);
}
void print()
{
    out=fopen("dfs.out","wt");
    fprintf(out,"%d ",cont);
    fclose(out);
}

void BFS(int startNode)
{

    cont++;
    int nod_curent,w=0;
    coada.push_back(startNode);
    vizitat.at(startNode) = 1;

    while( w<coada.size() )
    {

        nod_curent = coada.at(w);
        w++;
   //     coada.erase(coada.begin());
        list<int>:: iterator end_iterator = matrix.at(nod_curent).end();
        for(list<int>::iterator it=matrix.at(nod_curent).begin();it!=end_iterator;it++)
            if(!vizitat.at(*it))
            {
                coada.push_back(*it);
                vizitat.at(*it) = vizitat.at(nod_curent) + 1;
            }
    }

}