Cod sursa(job #2527149)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 19 ianuarie 2020 18:32:20
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include<fstream>
#include<vector>
#include<deque>

using namespace std;

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

int nrb;
int Niv[100005],Low[100005];
vector<int> A[100005],B[100005];
deque<pair<int,int> > S;

void dfs(int nod, int p, int niv)
{
    Niv[nod]=niv;
    Low[nod]=niv;

    for(auto other:A[nod])
    {
        if(other==p)
            continue;

        if(Niv[other]==0)
        {
            S.push_back({nod,other});
            dfs(other,nod,niv+1);
            Low[nod]=min(Low[nod],Low[other]);

            if(Low[other]>=Niv[nod])
            {
                nrb++;
                while(1)
                {
                    int aux=S.back().first;

                    B[nrb].push_back(S.back().second);
                    S.pop_back();

                    if(aux==nod)
                        break;
                }

                B[nrb].push_back(nod);
            }
        }
        else
            Low[nod]=min(Low[nod],Niv[other]);
    }
}

int main()
{
    int n,m;
    fi>>n>>m;

    for(int i=1; i<=m; i++)
    {
        int x,y;
        fi>>x>>y;

        A[x].push_back(y);
        A[y].push_back(x);
    }

    dfs(1,0,1);

    fo<<nrb<<"\n";
    for(int i=1; i<=nrb; i++)
    {
        for(auto x:B[i])
            fo<<x<<" ";
        fo<<"\n";
    }
    fi.close();
    fo.close();
    return 0;
}