Cod sursa(job #2839158)

Utilizator SmauSmau George Robert Smau Data 25 ianuarie 2022 13:24:17
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <fstream>
#include <vector>

#define NMAX 100028

using namespace std;

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

vector <int> G[NMAX];
bool used[NMAX];

int n, m, ans;

void DFS(int node) {
    used[node] = true;

    for(int i = 0; i < G[node].size(); i ++)
        if(!used[G[node][i]]) DFS(G[node][i]);
}

int main() {
    fin >> n >> m;
    for(int i = 1; i <= m; i ++) {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    for(int i = 1; i <= n; i ++)
        if(!used[i]) {
            DFS(i);
            ans ++;
        }

    fout << ans << '\n';

    return 0;
}