Cod sursa(job #2355949)

Utilizator cristiangeambasuCristian Geambasu cristiangeambasu Data 26 februarie 2019 13:34:22
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

void DFS(const vector<vector<int>> &graph, vector<int> &viz, int node) {
    viz[node] = 1;
    for(size_t i = 0; i < graph[node].size(); i++) {
        if(!viz[graph[node][i]]) {
            DFS(graph, viz, graph[node][i]);
        }
    }
}

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

    if(!fin.is_open() || !fout.is_open())
        return 1;

    vector<vector<int>> graph;
    vector<int> viz;
    int n, m, c = 0;

    fin >> n >> m;
    for(int i = 0; i < n; i++) {
        viz.push_back(0);
        graph.push_back(vector<int>());
    }

    for(int i = 0; i < m; i++) {
        int x, y;
        fin >> x >> y;

        graph[x].push_back(y);
    }

    for(int i = 0; i < n; i++) {
        if(!viz[i]) {
            c++;
            DFS(graph, viz, i);
        }
    }

    fout << c;

    fin.close();
    fout.close();

    return 0;
}