Cod sursa(job #2796013)

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

using namespace std;


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


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


    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);

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


        void AP();
        void addm(int n1, int n2)
        {
            adiacenta[n1].push_back(n2);
            adiacenta[n2].push_back(n1);
        }
};

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

}

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 :: AP()
{
    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.AP();
}

int main()
{
    p3();


    /*addm(1,2);
    addm(2,3);
    addm(3,4);
    addm(4,1);
    addm(1,5);
    addm(5,6);
    addm(6,7);
    addm(7,5);
    addm(7,8); */



    return 0;
}