Cod sursa(job #1464045)

Utilizator valentin50517Vozian Valentin valentin50517 Data 22 iulie 2015 10:15:17
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.51 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

vector<int> A[100010];
int N,M,X,Y,rs;
bool B[100010];
void DFS(int i){
	B[i] = true;
	for(int j = 0;j < A[i].size();j++){
		if(!B[A[i][j]]){
			DFS(A[i][j]);
		}
	}
}
int main(){
	fin >> N >> M;
	for(int i = 0;i<M;i++){
		fin >> X >> Y;
		A[X].push_back(Y);
		A[Y].push_back(X);
	}
	
	for(int i = 1;i <= N;i++){
		if(!B[i]){
			rs++;
			DFS(i);
		}
	}
	
	fout << rs;
	return 0;	
}