Cod sursa(job #1970798)

Utilizator borcanirobertBorcani Robert borcanirobert Data 19 aprilie 2017 16:45:14
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

using VI = vector<int>;
vector<VI> G;
int N, M;
vector<VI> cb;
VI low, ind;
vector<bool> u;
int nr;
stack<pair<int, int>> st;

void Read();
void BiconnectedComponents();
void DFS( int nod, int t );
void Add( int x, int y );
void WriteComponents();

int main()
{
    Read();
    BiconnectedComponents();
    WriteComponents();

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

void Read()
{
    int x, y;
    fin >> N >> M;
    G = vector<VI>(N + 1);
    low = ind = VI(N + 1);
    u = vector<bool>(N + 1);
    while ( M-- )
    {
        fin >> x >> y;

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

void BiconnectedComponents()
{
    for ( int i = 1; i <= N; ++i )
        if ( !ind[i] )
            DFS(i, 0);
}

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

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

        if ( !ind[v] )
        {
            st.push({nod, v});
            DFS(v, nod);
            low[nod] = min( low[nod], low[v] );

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

void Add( int x, int y )
{
    int a, b;
    VI n;

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

    for ( const int& x : n )
        u[x] = false;

    cb.push_back(n);
}

void WriteComponents()
{
    fout << cb.size() << '\n';
    for ( const auto& x : cb )
    {
        for ( const int& y : x )
            fout << y << ' ';
        fout << '\n';
    }
}