Cod sursa(job #2462773)

Utilizator robertstrecheStreche Robert robertstreche Data 27 septembrie 2019 19:59:27
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <bitset>

#define NMAX 100005

using namespace std;

bitset<NMAX> apparition;
vector<int> v[NMAX];

void dfs(int node) {
	apparition[node] = 1;

	for (auto iterator : v[node]) {
		if (!apparition[iterator]) {
			dfs(iterator);
		}
	}
}

int main() {
	ifstream cin("dfs.in");
	ofstream cout("dfs.out");

	int n, m;
	int x, y, totalNumber = 0;

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		cin >> x >> y;

		v[x].push_back(y);
		v[y].push_back(x);
	}

	for (int i = 1; i <= n; i++) {
		if (!apparition[i]) {
			totalNumber++;
			dfs(i);
		}
	}

	cout << totalNumber << '\n';
	
	cin.close();
	cout.close();

	return 0;
}