Cod sursa(job #710062)

Utilizator fhandreiAndrei Hareza fhandrei Data 8 martie 2012 21:29:51
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
//Include
#include <stdio.h>
#include <vector>
using namespace std;

//Constante
const int MAX_SIZE = 100001;

//Functii
void dfs(int start);

//Variabile
FILE *in, *out;

int nrNoduri, nrMuchii;
int componente;

vector<int> vizitat;
vector<int> graf[MAX_SIZE];

//Main
int main()
{
	in = fopen("dfs.in","rt");
	out = fopen("dfs.out","wt");
	fscanf(in, "%d%d", &nrNoduri, &nrMuchii);
	vizitat.resize(nrNoduri+1);
	
	int cFrom, cTo;
	for(int i=1 ; i <=nrMuchii ; ++i)
	{
		fscanf(in, "%d%d", &cFrom, &cTo);
		graf[cFrom].push_back(cTo);
	}
	
	for(int i=1 ; i <=nrNoduri ; ++i)
		if(!vizitat[i])
		{
			dfs(i);
			++componente;
		}
	
	fprintf(out, "%d", componente);
	
	fclose(in);
	fclose(out);
	return 0;
}

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