Cod sursa(job #2796269)

Utilizator Octavian21Chiriac Octavian Octavian21 Data 7 noiembrie 2021 20:18:05
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 5.64 kb
#include <bits/stdc++.h>

using namespace std;

/*
ifstream in("ctc.in");
ofstream out("ctc.out");
*/
ifstream in("biconex.in");
ofstream out("biconex.out");



class Graf
{
    int n , m;
    vector <vector <int>> adiacenta;
    vector <vector<int>> rev;

    int minim(int a, int b);
    void dfsCc(int nodp, vector<int>& prnt, vector<int>& desc, vector<int>& ret, stack<pair<int,int>>& st, int & cc ,vector <vector <int>>& compCon);

    void dfsNorm(int & nod, vector <bool>& viz, stack <int>& st);
    void revers(vector<vector<int>>& rev );
    void  dfsNorm2(int & nod, vector <bool>& viz,  /*vector<vector<int>>& rev,*/int & nrC ,vector <vector<int>>& solutii);

    public:
        Graf(int n, int m, vector <vector <int>> adiacenta);
        Graf(int n, int m, vector <vector <int>> adiacenta, vector <vector <int>> rev);

        void PA();

        void tareConexC();

};

Graf :: Graf(int n, int m, vector <vector <int>> adiacenta)
{
    this-> n = n;
    this-> m = m;
    this -> adiacenta = adiacenta ;
    /*for(int i = 0; i<= n; ++i)
    {
        this-> rev[i] = NULL;
    }*/

}
Graf :: Graf(int n, int m, vector <vector <int>> adiacenta, vector <vector<int>> rev)
{
    this-> n = n;
    this-> m = m;
    this -> adiacenta = adiacenta ;
    this -> rev = rev;

}

int Graf ::  minim(int a, int b)
{
    if(a>b)
        return b;
    return a;
}

void Graf :: dfsCc(int nodp, vector<int>& prnt, vector<int>& desc, vector<int>& ret , stack<pair<int,int>>& st, int & cc, vector <vector <int>>& compCon)
{
    static int timp = 1;
    desc[nodp] = timp;
    ret[nodp] = timp;
    timp ++;
    int nrc = 0;

    for(auto nodc: adiacenta[nodp])
    {
        if(desc[nodc] == -1)
        {
            nrc++;
            prnt[nodc] = nodp;
            st.push( make_pair (nodp,nodc));
            dfsCc(nodc,prnt,desc,ret,st,cc,compCon);

            ret[nodp] = minim(ret[nodp],ret[nodc]);

            if((prnt[nodp] == -1 && nrc > 1)  || (prnt[nodp] != -1 && desc[nodp]<= ret[nodc]))  // verific noduri sunt ap
            {

                while(st.top().first != nodp || st.top().second != nodc)
                {
                    compCon[cc].push_back(st.top().second);
                    st . pop();
                }
                compCon[cc].push_back(st.top().second);
                compCon[cc].push_back(st.top().first);

                st . pop();

                cc++;

            }
        }
        else if(nodc != prnt[nodp])
        {
            ret[nodp] = minim(ret[nodp], desc[nodc]);
        }
    }

}

void Graf :: PA()
{
    vector<int> prnt (n+1,-1), desc (n+1,-1), ret (n+1,-1);
    vector<bool> ap(n+1,false);
    stack<pair<int,int>> st;
    vector <vector <int>> compCon (n+1);
    int cc = 1;
    int chestie;

    for(int i = 1; i<= n; ++i)
    {
        if(desc[i] == -1)
        {
            dfsCc(i,prnt,desc,ret,st,cc,compCon);
        }
        while(! st.empty())
        {
            compCon[cc].push_back(st.top().second);
            chestie = st.top().first;
            st . pop();
        }
    }
    compCon[cc].push_back(chestie);

    out<<cc<<"\n";
    for(int i = 1;i<= cc; ++i)
    {
        for(auto j : compCon[i])
        {
            out<<j<<" ";
        }
        out<<"\n";
    }
}

void p3()
{
    int n,m,x,y;
    in>>n>>m;
    vector <vector <int>> adiacenta (n+1);

    for(int i =0; i<m; ++i)
    {
        in>>x>>y;
        adiacenta[x].push_back(y);
        adiacenta[y].push_back(x);
    }

    Graf g1 = Graf(n,m,adiacenta);

    g1.PA();
}


void Graf :: dfsNorm(int & nod, vector <bool>& viz, stack <int>& st)
{
    viz[nod] = true;
    //cout<<nod<<" ";
    for(int i : adiacenta[nod])
    {
        if( viz[i] == false)
        {
            viz[nod] = true;
            dfsNorm(i,viz,st);
            //st.push(i);

        }
    }
    st.push(nod);

}

void Graf :: dfsNorm2(int & nod, vector <bool>& viz, /*vector<vector<int>>& rev,*/int & nrC ,vector <vector<int>>& solutii)
{
    viz[nod] = true;
    solutii[nrC] . push_back(nod);
    //out<<nod<<" ";
    for(int i : rev[nod])
    {
        if( viz[i] == false)
        {
            viz[nod] = true;
            dfsNorm2(i,viz/*,rev*/,nrC,solutii);
            //st.push(i);

        }
    }

}

void Graf :: revers(vector<vector<int>>& rev )
{
    for(int i = 1; i<= n; ++i)
    {
        for(auto j: adiacenta[i])
        {
            rev[j].push_back(i);
        }
    }
}

void Graf :: tareConexC()
{
    stack <int> st;
    vector <bool> viz (n+1, false);
    vector <vector<int>> /*rev (n+1),*/ solutii (n+1);
    int nrC = 0;

    for(int i = 1;i <= n; ++i)
    {
        if(viz[i] == false)
        {
            dfsNorm(i,viz,st);
            //st.push(i);
        }
    }

    //revers(rev);

    for(int i =1; i<= n; ++i)
        viz[i] = false;

    while(! st.empty())
    {
        if(viz[st.top()] == false)
        {
            nrC ++;
            dfsNorm2(st.top(),viz,/*rev,*/nrC,solutii);
        }
        st.pop();
    }
    out<<nrC<<"\n";
    for(int i = 1;i<= nrC; ++i)
    {
        for(auto j : solutii[i])
        {
            out<<j<<" ";
        }
        out<<"\n";
    }

}


/*void p4 ()
{
    int n,m,x,y;
    in>>n>>m;
    vector <vector<int>> adiacenta (n+1), rev(n+1);
    for(int i = 1; i<=m ; ++i)
    {
        in>>x>>y;
        adiacenta[x].push_back(y);
        rev[y].push_back(x);
    }
    Graf g(n,m,adiacenta,rev);
    g.tareConexC();
}*/

int main()
{
    p3();
    //p4();

    return 0;
}