Cod sursa(job #894391)

Utilizator robertgbrrobertgbr robertgbr Data 26 februarie 2013 21:02:59
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
//BFS for computing a conexed graph
#include <iostream>
#include <cstdio>
#include <list>
#include <queue>
#define MAXN 1000

using namespace std;
bool vizitat[MAXN];
list<int> mylist[MAXN];
list<int>::iterator it;
queue<int> myqueue;
int nr,n,m;

int BFS(int i){
    if(myqueue.empty()){
        return 0;}
    else{
        for(it=mylist[i].begin();it!=mylist[i].end();it++){
            if(!vizitat[*it]){
                vizitat[*it]=1;
                myqueue.push(*it);}
        }
        myqueue.pop();
        return BFS(myqueue.front());
    }
}
int main()
{
    int x,y,i=0,last=-1;
    FILE *inFile;
    FILE *outFile;
    inFile = fopen("bfs.in","r");
    outFile= fopen("bfs.out","w");
    fscanf(inFile,"%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        fscanf(inFile,"%d",&x);
        fscanf(inFile,"%d",&y);
        mylist[x].push_back(y);
        mylist[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
    {
    if(!vizitat[i]){
        vizitat[i]=1;
        myqueue.push(i);
        BFS(i);
        nr++;
    }
    }
    fprintf(outFile,"%d",nr);
    fclose(inFile);
    fclose(outFile);
    return 0;
}