Cod sursa(job #2368580)

Utilizator AlexTudorAlex Brinza AlexTudor Data 5 martie 2019 16:39:48
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <bits/stdc++.h>
using namespace std;

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

const int NMAX=100005;
const int INF=2000000000;

int disc[NMAX],low[NMAX];

vector < int > Ad[NMAX];
vector < int > sol[NMAX];

stack <int> S;

int N,M;
int x,y,ct,nr;

void read()
{
    fin>>N>>M;

    for(int i=1;i<=M;++i)
    {
        fin>>x>>y;

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

void dfs(int nod, int parent )
{
    disc[nod] = low[nod] = ++ct;

    int w;

  //  for(int i=1;i<=N;++i) fout<<viz[i]<<" ";

    for(int i=0;i<Ad[nod].size();++i)
    {
        w=Ad[nod][i];

        if( w == parent ) continue;

        if( disc[w] ) low[nod] = min( low[nod], disc[w] );
        else
        {
            S.push(w);

            dfs(w, nod);

            low[nod] = min( low[nod], low[w] );

            if(low[w]>=disc[nod])
            {
                S.push(nod);

                nr++;

                while(!S.empty() && S.top()!=w )
                {
                  sol[nr].push_back(S.top());

                  S.pop();
                }

                if(!S.empty())
                {
                    sol[nr].push_back(S.top());

                    S.pop();
                }

            }

        }
    }


}

int main()
{
    read();

    dfs(1,0);

    fout<<nr<<"\n";
    for(int i=1;i<=nr;++i)
        {
         for(int j=0;j<sol[i].size();++j)
            fout<<sol[i][j]<<" ";
         fout<<"\n";
        }

    return 0;
}