Pagini recente » Cod sursa (job #1371262) | Cod sursa (job #2748296) | Cod sursa (job #56853) | Cod sursa (job #68806) | Cod sursa (job #2665450)
#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;
}