Cod sursa(job #1425114)

Utilizator GilgodRobert B Gilgod Data 26 aprilie 2015 18:14:14
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <fstream>
#include <vector>

#define NMAX 100001
const char IN[] = "dfs.in", OUT[] = "dfs.out";

using namespace std;

int N;
vector<int> G[NMAX];
bool state[NMAX];

inline void readData() {
	freopen(IN, "r", stdin);
	int M;
	scanf(" %d%d", &N, &M);
	for (int i = 0; i < M; ++i) {
		int s, d;
		scanf(" %d%d", &s, &d);
		G[s].push_back(d);
		G[d].push_back(s);
	}
	fclose(stdin);
}

void DFS(int nod){
	state[nod] |= 1;
	for (const int n : G[nod]) {
		if (!state[n]) DFS(n);
	}
}

int main() {
	int nrCC = 0;
	readData();
	for (int i = 1; i <= N; ++i) {
		if (!state[i]) {
			++nrCC;
			DFS(i);
		}
	}
	freopen(OUT, "w", stdout);
	printf("%d \n", nrCC);
	fclose(stdout);
}