Cod sursa(job #2606134)

Utilizator RaduNichitaRadu Nichita RaduNichita Data 27 aprilie 2020 02:18:58
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;



#define NMAX 100009

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

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

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

    void show_matrix() {
        for (int i = 1; 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<int> &visited) {
        visited[node] = 1;

        for (auto const &x: matrix[node]) {
            if (!visited[x]) {
                DFS_UTIL(x, visited);
            }
        }
    } 

    int DFS() {
        std::vector<int> visited(N + 1, 0);
        int conex = 0;
        for (int i = 1; i <= N; i++) {
            if (!visited[i]) {
                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;
}