Cod sursa(job #2796527)

Utilizator lalalaura_022Udroiu Laura-Ioana lalalaura_022 Data 8 noiembrie 2021 12:59:14
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 5.44 kb
#include <bits/stdc++.h>

using namespace std;

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

class graf
{
    int nr_noduri, nr_muchii;

    vector<vector<int> > lista_muchii;

    bool orientat;

    void DFSx(int nod, vector<int>&v);

public:

    graf();

    graf(int nr_noduri, int nr_muchii, bool orientat);

    ~graf() {}

    void BFS(int start);

    void DFS(int start);

    //void CTC_DFS(int k, vector<int>&vizitat);
    //void DFS_GT(int k, vector<int>&vizitat);
    //void CTC_final();

    void dfs_mic(int x, vector<bool> &vizitat, stack<int>&stiva);
    void TOPO();

};

graf::graf()
{
    nr_noduri = 0;
    nr_muchii = 0;
    orientat = 0;
}

graf::graf(int nr_noduri, int nr_muchii, bool orientat)
{
    int i = 0, nod1, nod2;

    lista_muchii.resize(nr_noduri+1);

    this->nr_noduri = nr_noduri;
    this->nr_muchii = nr_muchii;
    this->orientat = orientat;

    while(i < nr_muchii)
    {
        f>>nod1>>nod2;
        if(orientat)
            lista_muchii[nod1].push_back(nod2);
        else
        {
            lista_muchii[nod1].push_back(nod2);
            lista_muchii[nod2].push_back(nod1);
        }
        i++;
    }
}

///----------------------------------------------------------------------------------bfs
void graf::BFS(int inceput)
{
    int i = 0, nod_curent;

    queue<int> q;

    vector<int>vizitat;
    vector<int>distanta;

    q.push(inceput);

    do
    {
        vizitat.push_back(0);
        distanta.push_back(-1);
        i++;

    }
    while(i <= nr_noduri);

    vizitat[inceput] = 1;
    distanta[inceput] = 0;

    while(!q.empty())
    {
        nod_curent = q.front();
        q.pop();
        for (auto j = lista_muchii[nod_curent].begin(); j != lista_muchii[nod_curent].end(); j++)
            if(!vizitat[*j])
            {
                vizitat[*j] = 1;
                q.push(*j);
                distanta[*j] = distanta[nod_curent] + 1;
            }
    }
    int marime = distanta.size();
    for(i = 1; i < marime; i++)
        g<<distanta[i]<<" ";
}
///----------------------------------------------------------------------------------DFS

void graf::DFSx(int start, vector<int> &vizitat)
{
    vizitat[start] = 1;
    auto jos = lista_muchii[start].begin();
    auto sus = lista_muchii[start].end();
    auto j = jos;
    while(j != sus)
    {
        if(vizitat[*j] == 0)
            DFSx(*j, vizitat);
        j++;
    }
}

void graf::DFS(int start)
{

    int i = 0, nr_componente_conexe = 0,  marime;

    vector<int> vizitat;
    do
    {
        vizitat.push_back(0);
        i++;

    }
    while(i <= nr_noduri);

    marime = vizitat.size();

    for(i = 1; i < marime; i++)
        if(vizitat[i] == 0)
        {
            DFSx(i,vizitat);
            nr_componente_conexe++;
        }
    g<<nr_componente_conexe;
}
///----------------------------------------------------------------------------------CTC

/*void graf::CTC_DFS(int k, vector<int> &vizitat)
{
    int i;
    vizitat[k] = 1;
    for(i = 1; i <= nr_noduri; i++)
        if(!vizitat[i])
        {
            int marime = lista_muchii[k].size();
            int ok = 0;
            for(int j = 0; j <= marime && ok == 0; j++)
                if(lista_muchii[k][j] == i)
                {
                    ok = 1;
                    CTC_DFS(i,vizitat);
                }
        }

}
void graf::DFS_GT(int k, vector<int> &vizitat)
{
    int i;
    vizitat[k] = 1;
    for(i = 1; i <= nr_noduri; i++)
        if(vizitat[i] == 0)
        {
            int marime = lista_muchii[i].size();
            int ok = 0;
            for(int j = 0; j <= marime && ok == 0; j++)
                if(lista_muchii[i][j] == k)
                {
                    ok = 1;
                    DFS_GT(i,vizitat);
                }
        }
}

void graf::CTC_final()
{
    vector<int> ctc;
    vector<int> vizitat1;
    vector<int> vizitat2;

    int i = 0, j, k, nrc = 0;

    for(i = 1; i <= nr_noduri; i++)
        if(ctc[i] == 0)
        {
            k = 0;
            do
            {
                vizitat1.push_back(0);
                vizitat2.push_back(0);
                i++;

            }
            while(i <= nr_noduri);
            nrc++;
            CTC_DFS(i, vizitat1);
            DFS_GT(i, vizitat2);
            for(j = 1; j <= nr_noduri; j++)
                if(vizitat1[j] == 1 && vizitat2[j] == 1)
                    ctc[j] = nrc;

        }
}
*/
void graf::dfs_mic(int x, vector<bool>&vizitat, stack<int> &stiva)
{
   vizitat[x] = 1;
   int marime = lista_muchii[x].size(), i = 0;
   while(i < marime)
   {
       if(vizitat[lista_muchii[x][i]] == 0)
        dfs_mic(lista_muchii[x][i], vizitat, stiva);
       i++;
   }
   stiva.push(x);

}

void graf::TOPO()
{
    stack <int> stiva;
    vector<bool>vizitat;
    int i = 0;

    do{
        vizitat.push_back(0);
        i++;
    }while(i <= nr_noduri + 1);

    for(i = 1; i <= nr_noduri; i++)
        if(vizitat[i] == 0)
            dfs_mic(i, vizitat, stiva);
    while(stiva.empty() == 0)
    {
        g<<stiva.top()<<" ";
        stiva.pop();
    }
}

int main()
{
    int n, m, s;
    f>>n>>m;
    //------------------|
    //graf test(n,m,0); |
    //test.DFS(1);      |DFS
    //------------------|

    graf test(n,m,1);
    test.TOPO();

    return 0;
}