Cod sursa(job #2795836)

Utilizator Octavian21Chiriac Octavian Octavian21 Data 7 noiembrie 2021 01:50:15
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.94 kb
#include <bits/stdc++.h>

using namespace std;


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

int n ,m ;

vector<vector<int>> adiacenta (100001);
vector<vector<int>> compCon (100001);

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

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

void dfs(int nodp, vector<int>& prnt, vector<int>& desc, vector<int>& ret, vector<bool>& ap, stack<pair<int,int>>& st, int & cc)
{
    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));
            dfs(nodc,prnt,desc,ret,ap,st,cc);

            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);
                    //cout<<st.top().first<<" "<<st.top().second<<" si ";
                    st . pop();
                }
                compCon[cc].push_back(st.top().second);
                compCon[cc].push_back(st.top().first);
                //cout<<st.top().first<<" "<<st.top().second<<" \n";
                st . pop();
                //ap[nodp] = true;
                cc++;

            }
        }
        else if(nodc != prnt[nodp])
        {
            ret[nodp] = minim(ret[nodp], desc[nodc]);
            //if(desc[nodc] < desc[nodp])
                //st.push( make_pair (nodp,nodc));
        }
    }

}

void 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;
    int cc = 1;
    int chestie;

    for(int i = 1; i<= n; ++i)
    {
        if(desc[i] == -1)
        {
            dfs(i,prnt,desc,ret,ap,st,cc);
        }
        while(! st.empty())
        {
            compCon[cc].push_back(st.top().second);
            chestie = st.top().first;
            //cout<<st.top().first<<" "<<st.top().second<<"  ";
            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";
    }
    //for(int i = 1;i<= n; ++i)
       // cout<< i << " :"<< ap[i]<<"\n";
}


int main()
{
    int x,y;
    in>>n>>m;
    for(int i = 1;i<= m; ++i)
    {
        in>>x>>y;
        addm(x,y);
    }
    /*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); */


    AP();
    return 0;
}