Cod sursa(job #1360572)

Utilizator ooptNemes Alin oopt Data 25 februarie 2015 16:31:46
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
// dfs
#include <iostream>
#include <fstream>
#include <vector>

#define NMax 100005
#define pb push_back

using namespace std;

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

int n,m;
vector<int> V[NMax];
bool viz[NMax];

void read() {
	f>>n>>m;
	for (int i=1;i<=m;i++) {
		int a, b;
		f>>a>>b;
		V[a].pb(b);
		V[b].pb(a);
	}
}

void dfs(int node) {
	viz[node] = true;
	for (unsigned i=0;i<V[node].size();i++) {
		int vecin = V[node][i];
		if (!viz[vecin])
			dfs(vecin);
	}
}

void solve() {
	int comp = 0;
	for (int i=1;i<=n;i++) {
		if (!viz[i]) {
			comp++;
			dfs(i);
		}
	}

	g<<comp<<'\n';
}

int main() {

	read();
	solve();

	f.close(); g.close();
	return 0;
}