Cod sursa(job #3122966)

Utilizator florin.romulescuFlorin Romulescu florin.romulescu Data 21 aprilie 2023 13:31:26
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>

int n, m;
const int NMAX = 10000;
std::vector<int> adj[NMAX];
std::vector<bool> visited(n);

void read_input() {
        std::ifstream fin("dfs.in");
        fin >> n >> m;
        for (int i = 1, x, y; i <= m; i++) {
            fin >> x >> y; // muchie (x, y)
            adj[x].push_back(y);
            adj[y].push_back(x);
        }
        fin.close();
}

void BFS(int source) {
    std::queue<int> q;
    q.push(source);
    visited[source] = true;

    while (!q.empty()) {
        int t = q.front();
        q.pop();

        for (auto i = adj[t].begin(); i != adj[t].end(); ++i) {
            if (!visited[*i]) {
                q.push(*i);
                visited[*i] = true;
            }
        }
    }
}

int main() {
    read_input();
    int count = 0;

    for (int i = 0; i < n; ++i) {
        if (visited[i] == false) {
            BFS(i);
            count += 1;
        }
    }

    std::ofstream fout("dfs.out");
    fout << count;
    fout.close();
}