Pagini recente » Cod sursa (job #3316864) | Cod sursa (job #3314748) | Cod sursa (job #3318480) | Cod sursa (job #274651) | Cod sursa (job #3321622)
// https://infoarena.ro/problema/dfs
#include <fstream>
#include <vector>
#include <cstring>
std::ifstream in("dfs.in");
std::ofstream out("dfs.out");
void dfs(std::vector<unsigned>* graph, bool* found, unsigned entry) {
for (unsigned node : graph[entry]) {
if ( found[node] ) continue;
found[node] = true;
dfs(graph, found, node);
}
}
int main() {
unsigned nodes, edges;
in >> nodes >> edges;
std::vector<unsigned> graph[100001];
unsigned a, b;
for(unsigned edge = 0; edge < edges; edge += 1) {
in >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
bool found[100001];
std::memset(found, 0, sizeof(bool) * 100001);
size_t count = 0;
for(unsigned node = 0; node < nodes; node += 1) {
if( found[node] ) continue;
count += 1;
found[node] = true;
dfs(graph, found, node);
}
out << count;
}