Cod sursa(job #2606125)

Utilizator RaduNichitaRadu Nichita RaduNichita Data 27 aprilie 2020 01:14:29
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;



#define NMAX 100000

class Task {
    std::vector<int> matrix[NMAX];
    int N;
    int M;

    void read_input() {
        std::ifstream in("dfs.in");
        
        in >> N;
        in >> M;

        for (int i = 0; i < M; i++) {
            int x;
            int y;
            in >> x;
            in >> y;
            matrix[x].push_back(y);
        }

       


        in.close();
    }

    void show_matrix() {
        for (int i = 0; i < N; i++) {
            std::cout<<i<<":";
            for (int j = 0; j < matrix[i].size(); j++) {
                std::cout<<matrix[i][j]<<" ";
            }
            std::cout<<"\n";
        }
    }

    void DFS_UTIL(int node, std::vector<bool> &visited) {
        visited[node] = true;

        for (int i = 0; i < matrix[node].size(); i++) {
            if (visited[matrix[node][i]] == false) {
                DFS_UTIL(matrix[node][i], visited);
            }
        }
    } 

    int DFS() {
        std::vector<bool> visited(N + 1, false);
        int conex = 0;
        for (int i = 0; i < N; i++) {
            if (visited[i] == false) {
                DFS_UTIL(i, visited);
                conex++;
            }
        }
        return conex;
    }

    void print(int res) {
        std::ofstream out("dfs.out");   
        out<<res<<"\n";
        out.close();
        return;
    }

 public:
    void solve() {
        read_input();
        print(DFS());
    }

};



int main() {

    Task* task = new Task();
    task->solve();
    delete(task);

    return 0;
}