Pagini recente » Cod sursa (job #837199) | Cod sursa (job #2437176) | Cod sursa (job #2865913) | Cod sursa (job #2806551) | Cod sursa (job #2665444)
#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;
}