Cod sursa(job #1923594)

Utilizator sicsicFMI-Coteanu Vlad sicsic Data 11 martie 2017 17:46:41
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 2.32 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
#define Nmax 100005
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");

vector<int> bc[Nmax];
stack< pair<int,int> > S;
int nrbc = 0;

struct el{int first, second;};

void citire(int &n, vector<int> G[]) {
    int m, a, b;
    f >> n >> m;
    while(m--) {
        f >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
}

void bicon(int nod, int fiu){
    int x, y;
    nrbc++;
    do {
        x = S.top().first;
        y = S.top().second;
        S.pop();
        bc[nrbc].push_back(y);
    } while (x != nod && y != fiu);
    bc[nrbc].push_back(x);
}

void getCritical(int nod, vector<int> G[], int H[], int  Niv[], bitset<Nmax> &isCritic,
                      bitset<Nmax> &isUsed) {
    isUsed[nod] = 1;
    H[nod] = Niv[nod];
    for(int i = 0; i < G[nod].size(); ++i) {
        int j = G[nod][i];
        if(!isUsed[j]) {
            S.push(make_pair(nod, j));
            Niv[j] = Niv[nod] + 1;
            getCritical(j, G, H, Niv, isCritic, isUsed);
            H[nod] = min(H[nod], H[j]);
            if(H[j] >= Niv[nod]) {
               // g << nod << " * " << j << '\n';
                bicon(nod, j);
                isCritic[nod] = 1;
            }
        }
        else if (Niv[j] < Niv[nod] - 1)
            H[nod] = min(H[nod], Niv[j]);
    }
}

void adaug(vector<int> lista[], int nod, int j) {
    for(int i = 0; i < lista[nod].size(); ++i)
        if(lista[nod][i] == j) return;
    lista[nod].push_back(j);
}


int main()
{
    int N, H[Nmax], Niv[Nmax];
    vector<int> G[Nmax];
    bitset<Nmax> isUsed;
    bitset<Nmax> isCritic;
    isUsed.reset();
    isCritic.reset();
    citire(N, G);


    //pregatim proc
    for(int i = 0; i < Nmax - 10; ++i)
        H[i] = Niv[i]  = 0;
    getCritical(1 , G, H, Niv, isCritic, isUsed);
    // Puncte critice,
    //Verificam daca 1 este critic
    int ok = 0;
    for(int i = 1; i <= N; ++i)
        if(Niv[i] == 1)
            ok++;
    if(ok > 1)
        isCritic[1] = 1;
    else
        isCritic[1] = 0;
    g << nrbc << '\n';
    for(int i = 1; i <= nrbc; ++i) {
        for(int j = 0; j < bc[i].size(); ++j)
            g << bc[i][j] << " ";
        g << '\n';
    }
    return 0;
}