Cod sursa(job #2665444)

Utilizator TheSharkCristian-Andrei Ionescu TheShark Data 30 octombrie 2020 19:51:34
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include<iostream>
#include<unordered_map>
#include<list>

using namespace std;

void dfs(unordered_map<unsigned int, list<unsigned int>> graphAdjList, unsigned int startNode, bool isVisited[]) {
	isVisited[startNode] = true;

	for (auto node : graphAdjList[startNode]) {
		if (!isVisited[node]) {
			dfs(graphAdjList, node, isVisited);
		}
	}
}

int main() {

	unsigned int N, M;
	unordered_map<unsigned int, list<unsigned int>> graphAdjList;

	cin >> N >> M;
	for (unsigned int i = 0; i < M; ++i) {
		unsigned int startNode, endNode;
		cin >> startNode >> endNode;
		graphAdjList[startNode].push_back(endNode);
		graphAdjList[endNode].push_back(startNode);
	}

	bool* isVisited = new bool[N + 1]();
	unsigned int noOfConnectedComps = 0;
	for (unsigned int node = 1; node <= N; ++node) {
		if (!isVisited[node]) {
			dfs(graphAdjList, node, isVisited);
			++noOfConnectedComps;
		}
	}

	cout << noOfConnectedComps;

	return 0;
}