Cod sursa(job #3123239)

Utilizator adaxndDobrica Nicoleta Adriana adaxnd Data 22 aprilie 2023 18:05:07
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <vector>

#define NMAX 200000

using namespace std;

void dfs(int node, vector<int> adj[NMAX], vector<bool> &visited) {
    visited[node] = true;

    for (auto neigh : adj[node]) {
        if (!visited[neigh]) {
            dfs(neigh, adj, visited);
        }
    }
}

int dfs_main_function(int n, int m, vector<int> adj[NMAX]) {
    vector<bool> visited(n + 1, false);

    int connected_components = 0;

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

    return connected_components;
}

int main() {
    int n, m;

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

    fin >> n >> m;

    vector<int> adj[n + 1];

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

    fout << dfs_main_function(n, m, adj) << '\n';

    return 0;
}