Cod sursa(job #1528518)

Utilizator theodor.moroianuTheodor Moroianu theodor.moroianu Data 19 noiembrie 2015 19:50:46
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <fstream>
#include <vector>
using namespace std;

const int NMAX = 100001;
vector <int> v[NMAX];
int n, i, j, k, l, m;
bool agn[NMAX];
int r = 0;

void dfs(int x);

int main() {
	ifstream in("dfs.in");
	ofstream out("dfs.out");
	in >> n >> m;
	while (m--) {
		in >> i >> j;
		v[i].push_back(j);
		v[j].push_back(i);
	}
	for (i = 1; i <= n; ++i) {
		if (!agn[i]) {
			r++;
			dfs(i);
		}
	}
	in.close();
	out << r;
	out.close();
	return 0;
}


void dfs(int x) {
	agn[x] = 1;
	for (int q = 0; q < v[x].size(); q++) {
		if (!agn[v[x][q]])
			dfs(v[x][q]);
	}
}