Cod sursa(job #1319569)

Utilizator harababurelPuscas Sergiu harababurel Data 17 ianuarie 2015 09:46:51
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <iostream>
#include <fstream>
#include <vector>
#define nmax 100005
using namespace std;

int n, m, x, y, comps = 0;
bool seen[nmax];
vector <int> v[nmax];

void dfs(int x) {
	seen[x] = true;

	for(int i=0; i<v[x].size(); i++) {
		int y = v[x][i];
		if(!seen[y]) dfs(y);
	}
}

int main() {
	ifstream f("dfs.in");
	ofstream g("dfs.out");

	f>>n>>m;
	for(int i=1; i<=m; i++) {
		f>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}

/*
	for(int x=1; x<=n; x++) {
		cout<<"Vecinii lui "<<x<<" sunt: ";

		for(int i=0; i<v[x].size(); i++)
			cout<<v[x][i]<<" ";
		cout<<"\n";
	}
*/

	for(int i=1; i<=n; i++)
		if(!seen[i])
			++comps,
			dfs(i);

	g<<comps<<"\n";
	return 0;
}