Cod sursa(job #3123294)

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

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

void dfs(int node) {
    visited[node] = true;
    nodesStack.push(node);
    while (!nodesStack.empty()) {
        node = nodesStack.top();
        nodesStack.pop();
        for (auto neighbour : graph[node]) {
            if (!visited[neighbour]) {
                visited[neighbour] = true;
                nodesStack.push(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;
}