Cod sursa(job #1314748)

Utilizator anaid96Nasue Diana anaid96 Data 12 ianuarie 2015 11:37:52
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include<stdio.h>
#include<vector>

using namespace std;

//definitii
#define Nmax 100001

FILE *in,*out;

//variabile
int n, m;
int x, y;
int nrc;

vector<int> graf[Nmax];

bool viz[Nmax];

//functii
void parcurgere(int nod);

int main(void)
{
	in = fopen("dfs.in", "rt");
	out = fopen("dfs.out" , "wt");
	
	fscanf(in,"%d%d",&n,&m);
	
	for(int i=1; i<=m; ++i)
	{
		fscanf(in,"%d%d", &x,&y);
		graf[x].push_back(y);
		graf[y].push_back(x);
	}
	
	for(int i=1; i<=n; ++i)
	{
		if(!viz[i])
		{
			nrc++;
			viz[i] = true;
			parcurgere(i);
		}
	}
	
	fprintf(out,"%d", nrc);
	
	fclose(in);
	fclose(out);
	return 0;
}

void parcurgere(int nod)
{
	vector<int> :: iterator it, end = graf[nod].end();
	for( it = graf[nod].begin(); it!=end; it++)
	{
		if(!viz[*it])
		{
			viz[*it] = true;
			parcurgere(*it);
			
		}
	}
}