Cod sursa(job #2702776)

Utilizator vnedelcuVictor Andrei Nedelcu vnedelcu Data 5 februarie 2021 20:24:48
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <vector>

using namespace std;

void dfs(int node, vector<bool> & visited, vector<vector<int>> & graph) {
    visited[node - 1] = true;
    for (int neighbor: graph[node - 1]) {
        if (!visited[neighbor - 1]) {
            dfs(neighbor, visited, graph);
        }
    }
}

int main() {
    ifstream fin("dfs.in");
    int n, m;
    fin >> n >> m;

    vector<vector<int>> graph(n);
    for (int i = 0; i < m; i++) {
        int node1, node2;
        fin >> node1 >> node2;
        graph[node1 - 1].push_back(node2);
    }
    fin.close();

    vector<bool> visited(n, false);
    int no_connected_components = 0;
    for (int node = 1; node <= n; node++) {
        if (!visited[node - 1]) {
            dfs(node, visited, graph);
            no_connected_components++;
        }
    }

    ofstream fout("dfs.out");
    fout << no_connected_components;
    fout.close();

    return 0;
}