Cod sursa(job #1450973)

Utilizator GilgodRobert B Gilgod Data 15 iunie 2015 16:36:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <vector>
#include <list>
#include <bitset>

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

using namespace std;

list<int> G[NMAX];
int N, M;

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

bitset<NMAX> visited;

void DFS(int node) {
	visited[node].flip();
	for (auto& n : G[node]) {
		if (!visited[n]) DFS(n);
	}
}

int main() {
	readData();
	int CC_count = 0;
	for (int i = 1; i <= N; ++i) {
		if (!visited[i]) {
			DFS(i);
			++CC_count;
		}
	}
	fprintf(fopen(OUT, "w"), "%d\n", CC_count);
	return 0;
}