Cod sursa(job #2799137)

Utilizator Stefan_BerlinschiStefan-Cristian Berlinschi Stefan_Berlinschi Data 12 noiembrie 2021 14:39:08
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.08 kb
#include <iostream>
#include <list>
#include <fstream>
#include <stack>
#include <vector>

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();

    int* sortaret();
    void dfs_top(int &ind, int i, bool* vizitat, int* sortare);
};

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* graf::sortaret() {
    bool *vizitat = new bool[n];
    int *sortare = new int[n];
    for (int i = 0; i < n; i++) {
        vizitat[i] = false;
        sortare[i] = -1;
    }

    int ind = n - 1;

    for (int i = 0; i < n; i++) {
        if (!vizitat[i]) {
            dfs_top(ind, i, vizitat, sortare);
        }
    }

    delete[] vizitat;
    return sortare;
}

void graf::dfs_top (int &ind, int i, bool* vizitat, int* sortare) {
    vizitat[i] = true;

    list<int>::iterator it;

    for (it = ad[i].begin(); it != ad[i].end(); it++) {
        if (!vizitat[*it]) {
            dfs_top(ind, *it, vizitat, sortare);
        }
    }

    sortare[ind] = i;
    ind --;
}

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

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

    int* p = g.sortaret();
    for (int i = 0; i < n; i++) {
        fout << p[i] + 1 << " ";
    }
    return 0;
}