Cod sursa(job #677289)

Utilizator grigoritaiulianDeactivated Profile grigoritaiulian Data 9 februarie 2012 23:14:30
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>

#define INFINIT 0X3f3f3f
#define MAXIM_NODURI 100001

using namespace std;

fstream fin("dfs.in", ios::in), fout("dfs.out", ios::out);

int noduri, muchii, componente_conexe = 0;
int vizitat[MAXIM_NODURI];

vector < int > graf[MAXIM_NODURI];

inline void read()
{
	int x, y;
	fin >> noduri >> muchii;
	while(fin >> x >> y)
	{
		graf[x].push_back(y);
	}
	fin.close();
}

inline void parcurgere_in_adancime(int nod)
{
	vizitat[nod] = 1;

	int vecini = graf[nod].size();

	for(int i = 0; i < vecini; i++)
		if(vizitat[graf[nod][i]] == 0)
		{
			parcurgere_in_adancime(graf[nod][i]);
		}
}

int main()
{
	read();
	for(int i = 1; i <= noduri; i++)
	{
	    if(vizitat[i] == 0)
	    {
            componente_conexe++;
            parcurgere_in_adancime(i);
	    }
	}
	fout << componente_conexe << '\n';
    fout.close();
	return 0;
}