Cod sursa(job #2681939)

Utilizator IoanaNadIoana Nadia Puiu IoanaNad Data 7 decembrie 2020 13:39:05
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <vector>
using namespace std;

void DFS(int currentNode, vector<vector<int>>& arches, vector<int>& visited) {
	if (visited[currentNode] == 1)
		return;
	visited[currentNode] = 1;
	int length = arches[currentNode].size();
	for (int i = 1; i < length; ++i) {
		DFS(arches[currentNode][i] - 1, arches, visited);
	}
}

int main() {
	ifstream fin("dfs.in");
	ofstream fout("dfs.out");
	int N, M;
	fin >> N >> M;
	vector<vector<int>> arches(N, vector<int>(1, -1));
	vector<int> visited(N, 0);
	int x, y;
	for (int i = 0; i < M; ++i) {
		fin >> x >> y;
		arches[x - 1].push_back(y);
		arches[y - 1].push_back(x);
	}
	int numberComponents = 0;
	for (int i = 0; i < N; ++i) {
		if (visited[i] == 0) {
			DFS(i, arches, visited);
			++numberComponents;
		}
	}
	fout << numberComponents;
	return 0;
}