Pagini recente » Cod sursa (job #3358674) | Cod sursa (job #1310364) | Cod sursa (job #1310380) | Cod sursa (job #1011763) | Cod sursa (job #3321632)
// https://infoarena.ro/problema/bfs
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
std::ifstream in("bfs.in");
std::ofstream out("bfs.out");
void bfs(std::vector<unsigned>* graph, bool* found, unsigned entry) {
std::queue<unsigned> queue;
for(queue.push(entry); !queue.empty(); queue.pop()) {
found[queue.front()] = true;
for(unsigned node : graph[queue.front()]) if( !found[node] ) {
queue.push(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 = 1; node <= nodes; node += 1) {
if( found[node] ) continue;
count += 1;
bfs(graph, found, node);
}
out << count;
}