Cod sursa(job #970942)

Utilizator cont_de_testeCont Teste cont_de_teste Data 8 iulie 2013 02:37:11
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

#ifdef INFOARENA
	#define cin fin
	#define cout fout
#endif

ifstream fin("dfs.in");
ofstream fout("dfs.out");
const int NMax = 100100;

int N, M, solution;
vector<int> A[NMax];
bool ap[NMax];


inline void DFs(int node) {
	for (vector<int>::iterator it = A[node].begin(); it != A[node].end(); it++) {
		if (!ap[*it]) {
			ap[*it] = true;
			DFs(*it);
		}
	}
}

int main() {
	cin >> N >> M;
	for (int i = 1; i <= M; i++) {
		int X, Y;
		cin >> X >> Y;
		A[X].push_back(Y);
		A[Y].push_back(X);
	}
	
	for (int i = 1; i <= N; i++) {
		if (!ap[i]) {
			DFs(i);
			solution++;
		}
	}
	
	cout << solution << '\n';
}