Cod sursa(job #2195534)

Utilizator horiahoria1Horia Alexandru Dragomir horiahoria1 Data 16 aprilie 2018 18:19:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#include <vector>

void dfs(int node, std::vector<bool> &visited, std::vector<int> *adj) {
    visited[node] = true;
    for (auto &neighbour : adj[node]) {
        if (!visited[neighbour]) {
            dfs(neighbour, visited, adj);
        }
    }
}

int main() {

    std::ifstream in("dfs.in");
    std::ofstream out("dfs.out");

    int n, m;
    in >> n >> m;

    int nr = 0;
    std::vector<int> adj[n + 1];
    std::vector<bool> visited(n + 1, false);

    int i;
    int u, v;

    for (i = 0; i < m; ++i) {
        in >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for (i = 1; i <= n; ++i) {
        if (!visited[i]) {
            ++nr;
            dfs(i, visited, adj);
        }
    }

    out << nr;

    in.close();
    out.close();

    return 0;
}