Cod sursa(job #2915513)

Utilizator carmenacatrineiCarmen-Lorena Acatrinei carmenacatrinei Data 22 iulie 2022 22:48:52
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.29 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

class graf {

    vector < bool > vis;
    vector < vector < int > > muchii;

    void dfs(int node) {

        vis[node] = true;

        for (int index = 0; index < muchii[node].size(); ++index) {
            int nextNode = muchii[node][index];

            if (!vis[nextNode]) {
                dfs(nextNode);
            }
        }

    }

    int numarComponenteConexe() {

        int counter = 0;
        int n = muchii.size() - 1;

        vis.resize(n + 1, false);

        for (int node = 1; node <= n; ++node)
            if (!vis[node]) {
                ++counter;
                dfs(node);
            }
        return counter;
    }

    vector < int > bfs(int sursa) {
        int n = muchii.size() - 1;

        queue < int > coadaBfs;
        vector < int > listaBfs;
        listaBfs.resize(n + 1, -1);

        listaBfs[sursa] = 0;
        coadaBfs.push(sursa);

        while (!coadaBfs.empty()) {
            int nod = coadaBfs.front();
            coadaBfs.pop();

            for (int i = 0; i < muchii[nod].size(); ++i)
                if (listaBfs[muchii[nod][i]] == -1) {
                    listaBfs[muchii[nod][i]] = listaBfs[nod] + 1;
                    coadaBfs.push(muchii[nod][i]);
                }
        }

        return listaBfs;
    }

    void dfsSortareTopologica(int nod, stack < int > &topo) {

        vis[nod] = 1;

        for (int i = 0; i < muchii[nod].size(); ++i)
            if (vis[muchii[nod][i]] == 0)
                dfsSortareTopologica(muchii[nod][i], topo);

        topo.push(nod);
    }

public:

    void dfsInfoarena() {

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

        int n, m, x, y;

        in >> n >> m;

        muchii.resize(n + 1);

        for (int index = 1; index <= m; ++index) {
            in >> x >> y;

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

        out << numarComponenteConexe();
    }

    void bfsInfoarena() {

        ifstream in("bfs.in");
        ofstream out("bfs.out");

        int n, m, nod, x, y;

        in >> n >> m >> nod;

        muchii.resize(n + 1);

        for (int index = 1; index <= m; ++index) {
            in >> x >> y;

            muchii[x].push_back(y);
        }

        vector < int > raspuns = bfs(nod);

        for (int i = 1; i <= n; ++i)
            out << raspuns[i] << " ";
    }

    void sortareTopologicaInfoarena() {

        ifstream in("sortaret.in");
        ofstream out("sortaret.out");

        int n, m, x, y;
        stack < int > topo;

        in >> n >> m;

        vis.resize(n + 1, false);
        muchii.resize(n + 1);

        for (int index = 1; index <= m; ++index) {
            in >> x >> y;

            muchii[x].push_back(y);
        }

        for (int i = 1; i<= n; ++i)
            if (vis[i] == 0)
                dfsSortareTopologica(i, topo);

        while (!topo.empty()) {
            int val = topo.top();
            topo.pop();

            out << val << " ";
        }

    }

};

int main()
{
    graf g;

    g.sortareTopologicaInfoarena();

    return 0;
}