Cod sursa(job #2786086)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 20 octombrie 2021 11:02:03
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.79 kb
#include<fstream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;

class Graf {
    int n;
    int m;
    vector<int> v[100002];
    bool viz[100002];
public:
    Graf(int n, int m, pair<int, int> muchii[], bool directed);
    int nrComponenteConexe();
    vector<int> bfs(int srs);
    vector<int> sortareTopologica();
private:
    void dfs(int nod);
    void dfsSortare(int nod, vector<int> &noduriSortate);
};

Graf :: Graf(int n, int m, pair<int, int> muchii[], bool directed) {
    this->n = n;
    this->m = m;
    for (int i = 1; i <= m; i++) {
        v[ muchii[i].first ].push_back(muchii[i].second);
        if (!directed) {
            v[ muchii[i].second ].push_back(muchii[i].first);
        }
    }
}
int Graf :: nrComponenteConexe() {
    for (int i = 1; i <= n; i++) {
        viz[i] = false;
    }
    int nr = 0;
    for (int i = 1; i <= n; i++) {
        if (!viz[i]) {
            nr++;
            dfs(i);
        }
    }
    return nr;
}
void Graf :: dfs(int nod) {
    viz[nod] = true;
    for (int i = 0; i < v[nod].size(); i++) {
        if (!viz[ v[nod][i] ]) {
            dfs(v[nod][i]);
        }
    }
}
vector<int> Graf :: bfs(int srs) {
    vector<int> dist;
    dist.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        dist[i] = -1;
    }
    queue<int> q;
    q.push(srs);
    dist[srs] = 0;
    while (!q.empty()) {
        int nod = q.front();
        for (int i = 0; i < v[nod].size(); i++) {
            int vecin = v[nod][i];
            if (dist[vecin] == -1) {
                dist[vecin] = dist[nod] + 1;
                q.push(vecin);
            }
        }
        q.pop();
    }
    return dist;
}

vector<int> Graf :: sortareTopologica() {
    vector<int> noduriSortate;
    memset(viz, 0, sizeof(viz));
    for (int i = 1; i <= n; i++) {
        if (!viz[i]) {
            dfsSortare(i, noduriSortate);
        }
    }
    for (int i = 0; i < n / 2; i++) {
        swap(noduriSortate[i], noduriSortate[n - i - 1]);
    }
    return noduriSortate;
}

void Graf :: dfsSortare(int nod, vector<int> &noduriSortate) {
    viz[nod] = true;
    for (int i = 0; i < v[nod].size(); i++) {
        int vecin = v[nod][i];
        if (!viz[vecin]) {
            dfsSortare(vecin, noduriSortate);
        }
    }
    noduriSortate.push_back(nod);
}

int n, m, i;
pair<int, int> muchii[1000005];
ifstream fin ("sortaret.in");
ofstream fout("sortaret.out");
int main() {
    fin>> n >> m;
    for (i = 1; i <= m; i++) {
        fin>> muchii[i].first >> muchii[i].second;
    }
    Graf* graf = new Graf(n, m, muchii, true);
    vector<int> noduriSortate = graf->sortareTopologica();
    for (int i = 0; i < noduriSortate.size(); i++) {
        fout<< noduriSortate[i] <<" ";
    }
}