Cod sursa(job #2665450)

Utilizator TheSharkCristian-Andrei Ionescu TheShark Data 30 octombrie 2020 20:11:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include<fstream>
#include<vector>
#define NMAX 100001

using namespace std;

ifstream in("dfs.in");

ofstream out("dfs.out");

vector<unsigned int> adjList[NMAX];
bool isVisited[NMAX];

void dfs(unsigned int startNode) {
	isVisited[startNode] = true;

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

int main() {

	unsigned int N, M;

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

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

	out << noOfConnectedComps;

	return 0;
}