Cod sursa(job #797052)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 13 octombrie 2012 11:38:50
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");

int N, M, k;
vector <int> G[100001];
int viz[100001];

void DFS(int s){
	int i;
	viz[s] = 1;
	for (i = 0; i < G[s].size(); i++){
		if (!viz[G[s][i]])
			DFS(G[s][i]);
	}
}

int main(){
	int i, x, y, nr = 0;
	fin >> N >> M; 
	
	for (i = 0; i < M ; i++){
		fin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	
	for (i = 1; i <= N; i++)
		if (!viz[i]) {
			DFS(i);
			nr++;
		}
	
	fout << nr <<"\n";
}