Cod sursa(job #359144)

Utilizator iulia609fara nume iulia609 Data 25 octombrie 2009 20:47:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<stdio.h>
#include<vector>
#define MAXN 100001
using namespace std;

vector<int> A[MAXN];

int x, y, N, M, U[MAXN];


void DFS(int nod)
{ int i, dim;
	U[nod] = 1;
	dim = A[nod].size();
	for(i = 0; i < A[nod].size(); i++)
	   if(U[A[nod][i]] == 0) DFS(A[nod][i]);
}


int main()
{ int i, sol;

	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);

	scanf("%d%d", &N, &M);
	for(i = 1; i <= M; i++)
	   {
		scanf("%d%d", &x, &y);
		A[x].push_back(y);
		A[y].push_back(x);
	   }

	sol = 0;
	for(i = 1; i <= N; i++)
	   if(!U[i])
		{ 
			DFS(i);
			sol ++;
	    }

	printf("%d\n", sol);
}