Cod sursa(job #627357)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 29 octombrie 2011 17:43:37
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include<fstream>
#include<vector>
using namespace std;
int N, M, k;
vector <int> a[100001];
int v[100001], viz[100001];

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

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