Cod sursa(job #2847873)

Utilizator Teo_1101Mititelu Teodor Teo_1101 Data 11 februarie 2022 17:38:45
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb

#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

int desc[100001];
int low[100001];
bool vis[100001];

vector < int > Ad[100001];
vector < int > biconex[100001];
int nrc;

stack < int > S;

void DFS( int nod, int parent ){
    S.push( nod );
    desc[nod] = desc[parent] + 1;
    low[nod] = desc[nod];

    vis[nod] = 1;

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

        if( vis[w] == 0 ){

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

            if( low[w] >= desc[nod] && w != parent ){
                nrc++;
                S.push( nod );

                while( !S.empty() && S.top() != w ){
                    biconex[nrc].push_back( S.top() );
                    S.pop();
                }
                if( !S.empty() ){
                    biconex[nrc].push_back( S.top() );
                    S.pop();
                }
            }
        }
        else if( w != parent ){
            low[nod] = min( low[nod], desc[w]);
        }
    }
}
int main()
{
    int N, M;
    cin >> N >> M;

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

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

    DFS( 1, 0 );

    cout << nrc << '\n';
    for( int i = 1; i <= nrc; ++i ){
        for( int j = 0; j < biconex[i].size(); ++j )
            cout << biconex[i][j] << ' ';
        cout << '\n';
    }
}