Cod sursa(job #3321631)

Utilizator g.vladGociu Vlad g.vlad Data 10 noiembrie 2025 17:15:31
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb

// https://infoarena.ro/problema/bfs

#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

std::ifstream in("dfs.in");
std::ofstream out("dfs.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;
}