Cod sursa(job #2610131)

Utilizator diana.megeleaDiana Megelea diana.megelea Data 4 mai 2020 15:24:24
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>
using namespace std;
#define NMAX 100000

 

class Task {
  public:
    void solve() {
        read_input();
        print_output();
    }

  private:
    int n, m;
    int componente_conexe = 0;

    vector<int> lista_vecini[NMAX];

     void read_input() {
        ifstream fin("dfs.in");
        fin >> n >> m;

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

            lista_vecini[x].push_back(y);
            lista_vecini[y].push_back(x);
        }

        fin.close();
    }

    void do_dfs() {
        vector<bool> visited(n + 1, 0);

        for (int i = 1; i <= n; ++i) {
            if (!visited[i]) {
                ++componente_conexe;
                dfs(i, visited);
            }
        }
    }

    void dfs(int i, vector<bool> &visited) {
        visited[i] = 1;

        for (auto vecin : lista_vecini[i]) {
            if (!visited[vecin]) {
                dfs(vecin, visited);
            }
        }
    }

    void print_output() { 
        ofstream fout("dfs.out");
        fout << componente_conexe;
        fout.close();
    }

};

 

int main() {
    Task *task = new Task();
    task->solve();
    delete task;
    return 0;
}