Cod sursa(job #3152566)

Utilizator andu9andu nita andu9 Data 25 septembrie 2023 19:30:02
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <vector>
#include <bitset>

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

const int nMax = 1e5;

std::bitset<nMax> vis;

std::vector<std::vector<int>> graph;

void dfs (int node) {
    vis[node] = 1;
    for (int i : graph[node])
        if (!vis[i])
            dfs (i);
}

int main () {
    int n, m; fin >> n >> m;
    graph.assign (n, std::vector<int> ());

    for (int i = 0; i < m; i += 1) {
        int x, y; fin >> x >> y;
        x -= 1, y -= 1;

        graph[x].emplace_back (y);
        graph[y].emplace_back (x);
    }


    int res = 0;
    for (int i = 0; i < n; i += 1) {
        if (!vis[i])
            dfs (i), res += 1;
    }

    fout << '\n' << res;

    graph.clear ();
    fin.close (), fout.close ();
    return 0;
}