Cod sursa(job #884597)

Utilizator bzxbzxbzxGhiuzan Paul bzxbzxbzx Data 21 februarie 2013 01:07:46
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <fstream>
#include <vector>

using namespace std;

vector <long> vec[100001];
int sel[100001];
ifstream in ("dfs.in");
ofstream out ("dfs.out");

void read (vector <long> vec[], long m) {
	long a, b;
	for (long i = 0; i < m; i++) {
		in >> a >> b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
}

void DF (long x) {
	int i;
	sel[x] = 1;
	for (i = 0; i < vec[x].size(); i++)
		if (sel[vec[x][i]] == 0)
			DF (vec[x][i]);
}

int main() {
	long n, m, k = 0;
	in >> n >> m;
	read (vec, m);
	in.close();
	for (int i = 1; i <=n; i++)
		if (sel[i]==0) {
			k++;
			DF (i);
		}
	out << k;
	out.close();
	return 0;
}