Cod sursa(job #2797913)

Utilizator Stefan_BerlinschiStefan-Cristian Berlinschi Stefan_Berlinschi Data 10 noiembrie 2021 18:57:58
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.2 kb
#include <iostream>
#include <list>
#include <fstream>
#include <stack>

using namespace std;

// ifstream fin("input.txt");
// ofstream fout("output.txt");

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


class graf {
private:
    int n;
    bool este_orientat;
    list<int> *ad;

public:
    graf(int n=1, bool o=1) {
        this->n = n;
        this->este_orientat = o;
        this->ad = new list<int>[n];
    };

    void adaug_muchie(int v, int w) {
        if (este_orientat == 1)
            this->ad[v].push_back(w); 
        else {
            this->ad[v].push_back(w);
            this->ad[w].push_back(v);
        }
    };

    void BFS(int s);
    void distante(int s);

    void DFS(int s);
    void DFS_recursiv(int s, bool *vizitat);
    int nr_conexe();
};

void graf::BFS(int s) {
    bool *vizitat = new bool[n];
    for (int i = 0; i < n; i++) {
        vizitat[i] = false;
    }

    list<int> coada;
    vizitat[s] = true;
    coada.push_back(s);

    while(!coada.empty()) {
        list<int>::iterator i;

        s = coada.front();
        fout << s << " ";
        // fout << s+1 << " ";

        coada.pop_front();

        for (i = ad[s].begin(); i != ad[s].end(); i++) {
            if (vizitat[*i] == false) {
                vizitat[*i] = true;
                coada.push_back(*i);
            }
        }
    }
    delete[] vizitat;
}

void graf::distante(int s) {
    bool *vizitat = new bool[n];
    int *distante = new int[n];
    for (int i = 0; i < n; i++) {
        vizitat[i] = false;
        distante[i] = -1;
    }

    list<int> coada;
    vizitat[s] = true;
    coada.push_back(s);
    distante[s] = 0;

    while(!coada.empty()) {
        list<int>::iterator i;

        s = coada.front();
        coada.pop_front();

        for (i = ad[s].begin(); i != ad[s].end(); i++) {
            if (vizitat[*i] == false) {
                vizitat[*i] = true;
                distante[*i] = distante[s] + 1;
                coada.push_back(*i);
            }
        }
    }

    for (int i = 0; i < n; i++) {
        fout << distante[i] << " ";
    }

    delete[] vizitat;
    delete[] distante;
}

void graf::DFS(int s) {
    bool *vizitat = new bool[n];
    for (int i = 0; i < n; i++) {
        vizitat[i] = false;
    }

    DFS_recursiv(s, vizitat);
    delete[] vizitat;
}

void graf::DFS_recursiv(int s, bool *vizitat) {
    vizitat[s] = true;
    // fout << s << " ";

    list<int>::iterator it;

    for (it = ad[s].begin(); it != ad[s].end(); it++) {
        if (!vizitat[*it])
            DFS_recursiv(*it, vizitat);
    }
}

int graf::nr_conexe() {
    bool *vizitat = new bool[n];
    for (int i = 0; i < n; i++) {
        vizitat[i] = false;
    }
    int nr = 0;

    for (int i = 0; i < n; i++) {
        if (!vizitat[i]) {
            DFS_recursiv(i, vizitat);
            nr ++;
        }
    }

    delete[] vizitat;
    return nr;
}

int main() {
    int n, m, s, a, b;
    fin >> n >> m;
    graf g(n, 0);

    for (int i = 0; i < m; i++) {
        fin >> a >> b;
        g.adaug_muchie(a-1, b-1);
    }

    fout << g.nr_conexe();
    return 0;
}