Cod sursa(job #3205323)

Utilizator AlexZeuVasile Alexandru AlexZeu Data 19 februarie 2024 12:18:57
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>
using namespace std;

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

bitset<100005> visited;

void dfs(int currNode, vector<int> edges[]) {
    visited[currNode] = true;

    for (auto elem : edges[currNode]) {
        if (!visited[elem]) {
            dfs(elem, edges);
        }
    }
}

int main(void) {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    const int mxN = 1e5 + 5;

    int N, M;
    fin >> N >> M;
    vector<int> edges[mxN];

    for (int x, y; M; --M) {
        fin >> x >> y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }

    int components = 0;
    for (int node = 1; node <= N; ++node) {
        if (visited[node] == 0) {
            dfs(node, edges);
            components++;
        }
    }

    fout << components;

    return 0;
}