Pagini recente » Cod sursa (job #680840) | Cod sursa (job #212671) | Cod sursa (job #1045671) | Cod sursa (job #681340) | Cod sursa (job #2800842)
#include <fstream>
#include <vector>
enum NodeState {
NOT_VISITED, VISITED
};
struct Node {
std::vector<int> neighbours;
NodeState state = NOT_VISITED;
};
Node graph[100001];
int count, m, n, a, b;
std::ifstream fin("dfs.in");
std::ofstream fout("dfs.out");
void dfs(int nodeIndex) {
graph[nodeIndex].state = VISITED;
for (auto& subNodeIndex : graph[nodeIndex].neighbours) {
if (graph[subNodeIndex].state == NOT_VISITED) {
dfs(subNodeIndex);
}
}
}
int main() {
fin >> n >> m;
for (int i = 0; i < m; i++) {
fin >> a >> b;
graph[a].neighbours.push_back(b);
graph[b].neighbours.push_back(a);
}
for (int i = 1; i <= n; i++) {
if (graph[i].state == NOT_VISITED) {
count++;
dfs(i);
}
}
fout << count;
return 0;
}