Cod sursa(job #2796788)

Utilizator petru.burdusaBurdusa Petru petru.burdusa Data 8 noiembrie 2021 19:47:03
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.97 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;


class Graf{
public:
    Graf(){}
    void bfs()
    {

        ifstream in("bfs.in");
        ofstream out("bfs.out");
        in>>m_nrNoduri>>m_nrMuchii>>m_start;
        for(int i=0;i<m_nrMuchii;i++)
        {
            int x,y;
            in>>x>>y;
            m_list[x].push_back(y);
        }

        for(int i=1;i<=m_nrNoduri;i++)
        {
            m_viz[i]=2000000000;
        }
        m_viz[m_start]=0;
        m_q[1]=m_start;
        int p=1;
        int u=1;
        while(p<=u) //<=
        {
            int r=m_q[p];
            for(int i=0;i<(m_list[r].size());i++)
            {
                int e=m_list[r][i];
                // cout<<e<<' ';

                if(m_viz[r]+1<m_viz[e])
                {
                    m_viz[e]=m_viz[r]+1;
                    u++;
                    m_q[u]=e;


                }
            }
            p++;
        }
        for(int i=1;i<=m_nrNoduri;i++)
        {
            if(m_viz[i]!=2000000000)
                out<<m_viz[i]<<' ';
            else
                out<<"-1 ";
        }
    }

    void r_dfs(int q)
    {
        m_viz[q]=1;
        for(int i=0;i<m_list[q].size();i++)
        {
            int r=m_list[q][i];

            if(m_viz[r]==0)
            {
                r_dfs(r);
            }
        }
    }

    void dfs()
    {

        ifstream in("dfs.in");
        ofstream out("dfs.out");
        in>>m_nrNoduri>>m_nrMuchii;
        for(int i=0;i<m_nrMuchii;i++)
        {
            int x,y;
            in>>x>>y;
            m_list[x].push_back(y);
            m_list[y].push_back(x);
        }

        int s=0;
        for(int i=1;i<=m_nrNoduri;i++)
        {
            if(m_viz[i]==0)
            {
                r_dfs(i);
                s++;
            }
        }
        r_dfs(1);
        out<<s<<'\n';
    }

    void sorttop_recursie(int q)
    {
        int i;
        m_viz[q]=1;

        for(i=0;i<m_list[q].size();i++)
        {
            int t=m_list[q][i];
            if(m_viz[t]==0)
            {
                sorttop_recursie(t);

            }

        }
        m_aux++;
        m_ordtop[m_aux]=q;
    }

    void sorttop()
    {

        ifstream in("sortaret.in");
        ofstream out("sortaret.out");
        int i;
        for(i=1;i<=m_nrMuchii;i++)
        {
            int x,y;
            in>>x>>y;
            m_list[x].push_back(y);
            m_grad[y]++;
        }
        for(i=1;i<=m_nrNoduri;i++)
        {
            if(m_grad[i]==0 && m_viz[i]==0)
            {
                sorttop_recursie(i);
            }
        }
        //cout<<w<<'\n';
        for(i=m_aux;i>0;i--)
        {
            out<<m_ordtop[i]<<' ';
        }
    }

private:

    int m_nrMuchii;
    int m_nrNoduri;
    int m_start;
    int m_viz[100001];
    int m_q[100001];
    int m_grad[100001];
    int m_ordtop[100001];
    int m_aux=0;
    vector<int> m_list[100001];

};

int main() {
    Graf graf;
    graf.sorttop();
}