Cod sursa(job #1758237)

Utilizator preda.andreiPreda Andrei preda.andrei Data 16 septembrie 2016 20:39:21
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

#define NMAX 100001

struct Nod
{
    int timp;
    int low;
    vector<int> vecini;
};

Nod noduri[NMAX];
vector< pair<int, int> > stiva;
vector< vector<int> > componente;
int timp = 0;

void aflaComponente(int nod);
void adaugaComponenta(int a, int b);

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

    int n, m;
    fin >> n >> m;

    while (m--) {
        int x, y;
        fin >> x >> y;
        noduri[x].vecini.push_back(y);
        noduri[y].vecini.push_back(x);
    }

    aflaComponente(1);

    fout << componente.size() << "\n";
    for (auto comp : componente) {
        for (int nod : comp)
            fout << nod << " ";
        fout << "\n";
    }

    return 0;
}

void aflaComponente(int nod)
{
    noduri[nod].timp = noduri[nod].low = ++timp;

    for (int v : noduri[nod].vecini) {
        if (noduri[v].timp <= 0) {
            stiva.push_back({nod, v});
            aflaComponente(v);
            noduri[nod].low = min(noduri[nod].low, noduri[v].low);
            if (noduri[v].low >= noduri[nod].timp) {
                adaugaComponenta(nod, v);
            }
        }
        else {
            noduri[nod].low = min(noduri[nod].low, noduri[v].timp);
        }
    }
}

void adaugaComponenta(int a, int b)
{
    vector<int> comp;
    while (stiva.back().first != a) {
        comp.push_back(stiva.back().second);
        stiva.pop_back();
    }

    comp.push_back(stiva.back().second);
    comp.push_back(stiva.back().first);
    stiva.pop_back();

    componente.push_back(comp);
}