Cod sursa(job #3123293)

Utilizator radustn92Radu Stancu radustn92 Data 22 aprilie 2023 21:39:18
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int N, M;
vector<bool> visited;
vector<vector<int>> graph;

void dfs(int node) {
    visited[node] = true;
    for (auto neighbour : graph[node]) {
        if (!visited[neighbour]) {
            dfs(neighbour);
        }
    }
}

int main() {
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);

    cin >> N >> M;
    graph.assign(N + 1, vector<int>());
    int x, y;
    for (int idx = 0; idx < M; idx++) {
        cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    visited.assign(N + 1, false);
    int result = 0;
    for (int node = 1; node <= N; node++) {
        if (!visited[node]) {
            result++;
            dfs(node);
        }
    }
    cout << result << "\n";
    return 0;
}