Cod sursa(job #651351)

Utilizator PetroiuDorinPetroiu Dorin ALexandru PetroiuDorin Data 20 decembrie 2011 09:14:08
Problema BFS - Parcurgere in latime Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 0.93 kb
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

int main()
{

	FILE * f = fopen("dfs.in", "r");
	int n, m ;
	fscanf(f, "%i%i", &n, &m);
	vector<vector<int> > a(n);
	vector<int> viz(n);

	int i, q, w;

	for (i = 0; i < n; i++)
{
		viz[i] = 0;
}
	for (i = 0; i < m; i++)
{
		fscanf(f, "%i%i", &q, &w);
		a[q-1].push_back(w-1);
		a[w-1].push_back(q-1);
		
}

	fclose(f);
	queue<int> coada;
	
	int conex = 0;
	for (int k = 0; k < n; k++)
	{
        if (viz[k] == 0)
{
         conex++;
         viz[k] = 1;
         coada.push(k);

       	while(!coada.empty())
{
       	int e = coada.front();
        coada.pop();
                
        int len = a[e].size();
for (i = 0; i < len; i++)
{
    if (viz[a[e][i]] == 0)
{
    coada.push(a[e][i]);
       viz[a[e][i]] = viz[e] + 1;
}
}
}
}
}

	f = fopen("dfs.out", "w");
	fprintf(f,"%i", conex);
	fclose(f);
	return 0;

}