Cod sursa(job #2742457)

Utilizator SergiuS3003Sergiu Stancu Nicolae SergiuS3003 Data 20 aprilie 2021 23:07:15
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#define pb push_back
#define nl '\n'
#define pii pair<int,int>
#define mp make_pair
using namespace std;
ifstream f ( "biconex.in" );
ofstream g ( "biconex.out" );
const int NMAX = 100005, MMAX = 2 * NMAX;
pii m[MMAX];
stack<pii>S;
vector<int>G[NMAX];
int dfn[NMAX], low[NMAX];
int compbiconex[MMAX], nrcomp;
vector<vector<int>>C;
void Stergmuchii ( int x, int y )
{
    nrcomp++;
    int tx, ty;
    vector<int>comp;

    do
    {
        tx = S.top().first;
        ty = S.top().second;
        S.pop();

        if ( compbiconex[tx] != nrcomp )
        {
            compbiconex[tx] = nrcomp;
            comp.pb ( tx );
        }

        if ( compbiconex[ty] != nrcomp )
        {
            compbiconex[ty] = nrcomp;
            comp.pb ( ty );
        }
    }
    while ( tx != x || ty != y );

    C.pb ( comp );
}
void DFS ( int x, int father, int number )
{
    dfn[x] = number;
    low[x] = number;

    for ( auto i : G[x] )
    {
        if ( i == father )
            continue;

        if ( dfn[i] == -1 )
        {
            S.push ( mp ( x, i ) );
            DFS ( i, x, number + 1 );
            low[x] = min ( low[x], low[i] );

            if ( low[i] >= dfn[x] )
                Stergmuchii ( x, i );
        }
        else  low[x] = min ( low[x], dfn[i] );
    }
}
int main()
{
    int N, M;
    f >> N >> M;

    for ( int i = 1; i <= M; i++ )
    {
        int x, y;
        f >> x >> y;
        G[x].pb ( y );
        G[y].pb ( x );
    }

    for ( int i = 1; i <= N; i++ )
        dfn[i] = -1;

    DFS ( 1, 0, 0 );
    g << C.size() << nl;

    for ( auto i : C )
    {
        for ( auto j : i )
            g << j << ' ';

        g << nl;
    }

    return 0;
}