Pagini recente » Cod sursa (job #1299742) | Cod sursa (job #1141006) | Cod sursa (job #536189)
Cod sursa(job #536189)
/*
FACUTA CU
PARCURGEREA BREADTH FIRST SEARCH
*/
#include<stdio.h>
#include<vector>
#include<list>
using namespace std;
FILE *in,*out;
vector < list<int> > matrix;
vector < int > vizitat;
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]==0)
BFS(i);
}
print();
return 0;
}
void read()
{
int i,x,y;
in=fopen("dfs.in","rt");
fscanf(in,"%d%d",&varfuri,&muchii);
matrix.resize(varfuri+1);
vizitat.resize(varfuri+1);
for(i=1;i<=muchii;i++)
{
fscanf(in,"%d%d",&x,&y);
if(x!=y)
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;
}
}
}