Cod sursa(job #1857032)

Utilizator borcanirobertBorcani Robert borcanirobert Data 25 ianuarie 2017 18:55:19
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

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

using VI = vector<int>;
vector<VI> G;
VI low, a;
int N;
vector<VI> C;
stack< pair<int, int> > st;
vector<bool> u;

void ReadGraph();
void DFS( int nod, int t, int nr );
void Add( int x, int y );
void Write();

int main()
{
    ReadGraph();
    DFS(1, 0, 0);
    Write();

    fin.close();
    fout.close();
    return 0;
}

void ReadGraph()
{
    int M, x, y;

    fin >> N >> M;
    G = vector<VI>(N + 1);
    a = VI(N + 1, -1);
    low = VI(N + 1, N + 1);
    u = vector<bool>(N + 1);
    while ( M-- )
    {
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void DFS( int nod, int t, int nr )
{
    a[nod] = low[nod] = nr;

    for ( const auto& v : G[nod] )
    {
        if ( v == t ) continue;

        if ( a[v] == -1 )   // vecinul v inca nu a fost parcurs
        {
            st.push({nod, v});
            DFS(v, nod, nr + 1);
            low[nod] = min( low[nod], low[v] );

            if ( a[nod] <= low[v] )
                Add(nod, v);
        }
        else
        {
            low[nod] = min( low[nod], low[v] );
        }
    }
}

void Add( int x, int y )
{
    int i, j;
    VI n;
    u = vector<bool>(N + 1, 0);

    do
    {
        i = st.top().first, j = st.top().second;
        if ( !u[i] )
        {
            n.push_back(i);
            u[i] = true;
        }
        if ( !u[j] )
        {
            n.push_back(j);
            u[j] = true;
        }
        st.pop();
    }while ( !st.empty() && !( i == x && j == y ) );

    C.push_back(n);
}

void Write()
{
    fout << C.size() << '\n';

    for ( const auto& x : C )
    {
        for ( const auto& y : x )
            fout << y << ' ';
        fout << '\n';
    }
}