Cod sursa(job #3123439)

Utilizator LucianPandelicaPandelica Lucian LucianPandelica Data 23 aprilie 2023 18:04:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <bits/stdc++.h>
using namespace std;

static constexpr int NMAX = (int)1e5 + 5; // 10^5 + 5 = 100.005

int n, m;

vector<int> adj[NMAX];

ifstream f("dfs.in");
ofstream g("dfs.out");

void DFS_rec(int node, vector<int> &p) {

    for (int i = 0; i < adj[node].size(); i++) {
        if (p[adj[node].at(i)] == 0) {
            p[adj[node].at(i)] = node;
            DFS_rec(adj[node].at(i), p);
        }
    }
}

void solve() {
    int num_comp = 0;

    vector<int> p(n + 1, 0);

    for (int i = 1; i <= n; i++) {
        if (p[i] == 0) {
            num_comp++;
            DFS_rec(i, p);
        }
    }

    g << num_comp;
}

int main() {

    f >> n >> m;
    for (int i = 1, x, y; i <= m; i++) {
        f >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    f.close();

    solve();

    return 0;
}