Cod sursa(job #2518892)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 6 ianuarie 2020 18:13:21
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <bits/stdc++.h>
#define Dim 100001
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");

vector < int > V[Dim],A[Dim];
stack < int > S;

int N,M,low[Dim],x,y,lvl[Dim],viz[Dim],ans;

void DFS(int nod,int niv)
{
    low[nod]=lvl[nod]=niv; // modificari self cellll
    S.push(nod);
    viz[nod]=1;

    for(unsigned int i=0;i<V[nod].size();i++)
    {
        int vecin=V[nod][i];
        if( !viz[vecin] )
        {

            DFS(vecin,niv+1);
            low[ nod ]=min( low[ nod ] , low[ vecin ]); //  mnodificar pe stari
            if( low[ vecin ] >= lvl[ nod ] )
            {
                ans++;
                while( S.top() != vecin )
                {
                    A[ans].push_back( S.top() );
                    S.pop();
                }
                A[ans].push_back( vecin );
                A[ans].push_back( nod );
                S.pop();
            }
        }
        else
        if( viz[ vecin ] == 1 )
        low[ nod ]=min( low[ nod ] , lvl [ vecin ] );
    }

    viz[nod]=2;
}

int main()
{
    f>>N>>M;
    for(int i=1;i<=M;i++)
    {
        f>>x>>y;
        V[x].push_back(y);
        V[y].push_back(x);
    }
    for(int i=1;i<=N;i++)
    if(!viz[i])
    DFS(i,1);

    g<<ans<<'\n';
    for(int i=1;i<=ans;i++)
    {
        for(int j=0;j<A[i].size();j++) g<<A[i][j]<<" ";
        g<<'\n';
    }


    return 0;
}