Cod sursa(job #2797156)

Utilizator petru.burdusaBurdusa Petru petru.burdusa Data 9 noiembrie 2021 13:33:53
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 7.27 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

vector<int> listAux[100001];
vector<int> tareConexe[100001];
int nrTC=0;

bool cmp(const pair<int,int> &a,
         const pair<int,int> &b)
{
    return (a.second > b.second);
}

class Graf{
public:
    Graf(){}
    void citire_dfs()
    {
        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);
        }
    }
    void bfs()
    {
        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);
            }


        }
        m_stiva.push_back(q);
    }

    void rr_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)
            {
                rr_dfs(r);
            }


        }
        tareConexe[nrTC].push_back(q);
    }

    void dfs()
    {
        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()
    {
        int i;
        in>>m_nrNoduri>>m_nrMuchii;
        for(i=0;i<m_nrNoduri;i++)
        {
            m_grad.push_back(0);
            m_ordtop.push_back(0);
        }
        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]<<' ';
        }
    }

    void havelHakimi()
    {
        int s=0;
        in>>m_nrNoduri;
        for(int i=1;i<=m_nrNoduri;i++)
        {
            int x;
            in>>x;
            s+=x;
            m_nodGrad.push_back(make_pair(i,x));
            sort(m_nodGrad.begin(), m_nodGrad.end(),cmp);
        }

        if(s%2==0)
        {
            /*for(int i=0;i<m_nrNoduri;i++)
                cout<<m_nodGrad[i].second;
            cout<<'\n';
            for(int i=0;i<m_nrNoduri;i++)
                cout<<m_nodGrad[i].first;
            cout<<"\n\n";*/
            for(int i=1;i<=m_nrNoduri;i++)
            {
                if(m_nodGrad[i-1].second <= m_nrNoduri - i)
                {
                    int aux = m_nodGrad[i-1].second;
                    for(int j = 1; j <= aux; j++)
                    {
                        m_nodGrad[i+j-1].second--;
                        m_nodGrad[i-1].second--;
                        m_list[m_nodGrad[i-1].first].push_back(m_nodGrad[i+j-1].first);
                        m_list[m_nodGrad[i+j-1].first].push_back(m_nodGrad[i-1].first);
                    }
                }
                else
                {
                    out<<"-1";
                    return;
                }
                sort(m_nodGrad.begin()+i, m_nodGrad.end(),cmp);
                /*for(int i=0;i<m_nrNoduri;i++)
                    cout<<m_nodGrad[i].second;
                cout<<'\n';
                for(int i=0;i<m_nrNoduri;i++)
                    cout<<m_nodGrad[i].first;
                cout<<"\n\n";*/
            }
            int ok = 1;
            for(int i=0;i<m_nrNoduri;i++)
            {
                if(m_nodGrad[i].second != 0)
                    ok = 0;
            }
            if(ok==1)
            {
                for(int i = 1; i <= m_nrNoduri; i++)
                {
                    out<<i<<": ";
                    for(int j = 0; j < m_list[i].size(); j++)
                    {
                        out<<m_list[i][j]<<' ';
                    }
                    out<<'\n';
                }
            }
            else
            {
                out<<"-1";
                return;
            }

        }
        else
        {
            out<<"-1";
            return;
        }
    }

    void ctc_Kosoraju()
    {

        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);
            listAux[y].push_back(x);
        }
        for(int i=1;i<=m_nrNoduri;i++)
        {
            if(m_viz[i]==0)
            {
                r_dfs(i);
            }

        }
        for(int i=1;i<=m_nrNoduri;i++)
        {
            m_list[i].clear();
            for(int j=0;j<listAux[i].size();j++)
            {
                m_list[i].push_back(listAux[i][j]);
            }
        }
        /*for(int i=1;i<=m_nrNoduri;i++)
        {
            cout<<i<<": ";
            for(int j=0;j<listAux[i].size();j++)
            {
                cout<<m_list[i][j]<<' ';
            }
            cout<<'\n';
        }*/
        for(int i=0; i<=m_nrNoduri;i++)
            m_viz[i]=0;
        for(int i=m_stiva.size()-1;i>=0;i--)
        {
            if(m_viz[m_stiva[i]]==0)
            {
                nrTC++;
                rr_dfs(m_stiva[i]);
            }


        }
        out<<nrTC<<'\n';
        for(int i = 1; i <= nrTC; i++)
        {
            for(int j = 0; j < tareConexe[i].size();j++)
                out<<tareConexe[i][j]<<' ';
            out<<'\n';
        }


    }


private:

    int m_nrMuchii;
    int m_nrNoduri;
    int m_start;
    int m_viz[100001];
    int m_q[100001];
    vector<int> m_ordtop;
    vector<int> m_grad;
    vector<int> m_stiva;
    vector<pair<int,int>> m_nodGrad;
    int m_aux;
    vector<int> m_list[100001];

};

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