Pagini recente » Cod sursa (job #139354) | Cod sursa (job #1918587) | Cod sursa (job #2263563) | Cod sursa (job #521155) | Cod sursa (job #894391)
Cod sursa(job #894391)
//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;
}