Cod sursa(job #2376600)

Utilizator petru.ciocirlanPetru Ciocirlan petru.ciocirlan Data 8 martie 2019 16:39:46
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.04 kb
#include <algorithm>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

#define FILE_NAME "biconex"
ifstream in (FILE_NAME".in");
ofstream out(FILE_NAME".out");

const int MAX_NODES = 100000 + 4;
const int MAX_EDGES = 200000 + 4;
vector < int > G[MAX_NODES];
vector < vector < int > > CB;
vector < int > Level, Return;
stack < pair < int, int > > Stiva;
int N, M;

void add_compbiconexa(int x, int y)
{
    vector < int > compBiconexa;
    int tx, ty;
    do
    {
        tx = Stiva.top().first, ty = Stiva.top().second;
        Stiva.pop();
        compBiconexa.push_back(tx);
        compBiconexa.push_back(ty);
    } while(tx != x || ty != y);
    CB.push_back(compBiconexa);
}

void compute_compbiconexe(int nod, int father, int lvl)
{
    Return[nod] = Level[nod] = lvl;
    for(auto next = G[nod].cbegin(), fin = G[nod].cend(); next != fin; ++next)
    {
        if(*next != father)
        {
            if(Level[*next] == -1)
            {
                Stiva.push(make_pair(nod, *next));
                compute_compbiconexe(*next, nod, lvl + 1);
                Return[nod] = min(Return[nod], Return[*next]);
                if(Return[*next] >= Level[nod])
                    add_compbiconexa(nod, *next);
            }
            else
                Return[nod] = min(Return[nod], Level[*next]);
        }
    }
}

void read_input()
{
    in >> N >> M;
    while(M--)
    {
        int x, y;
        in >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    Level.resize(N+1), Return.resize(N+1);
    Level.assign(N+1, -1);
}

int main()
{
    read_input();
    compute_compbiconexe(1, 0, 0);

    out << CB.size() << '\n';
    for(auto it = CB.begin(), fin = CB.end(); it != fin; ++it)
    {
        sort(it->begin(), it->end());
        it->erase(unique(it->begin(), it->end()), it->end());
        for(auto zit = it->cbegin(), zfin = it->cend(); zit != zfin; ++zit)
            out << *zit << ' ';
        out << '\n';
    }

    return 0;
}