Cod sursa(job #1028093)

Utilizator bughybv31bogdan bughybv31 Data 13 noiembrie 2013 17:20:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <stdio.h>
#include <vector>
using namespace std;
#define N 100010
#define M 500010
vector <int> graf[N];
int n , m;
int viz[N];
int nr;
void citire()
{
	scanf ("%d %d\n" , &n , &m);
	while (m--)
	{
		int x , y;
		scanf ("%d %d\n" , &x , &y);
		//viz[x] = 1;
		graf[x].push_back(y);
		graf[y].push_back(x);
	}
}
void adancime (int i)
{
	for (unsigned int j = 0 ; j < graf[i].size() ; ++j)
	{
			if (!viz[graf[i][j]])
			{
				viz[graf[i][j]] = 1;
				int nod = graf[i][j];
				adancime (nod);
			}
		
	}
}
int main()
{
	freopen ("dfs.in","r",stdin);
	freopen ("dfs.out","w",stdout);
	citire();
	for (int i = 1 ; i <= n ; ++i)
	{
		if (viz[i] == 0)
		{	
			nr++;
			adancime(i);
		}
	}
	printf("\n");
	printf("%d",nr);
	return 0;
}