Cod sursa(job #2502897)

Utilizator CiboAndreiAndrei Cibo CiboAndrei Data 1 decembrie 2019 19:43:48
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <bits/stdc++.h>

using namespace std;

//#define f cin
//#define g cout
ifstream f("biconex.in");
ofstream g("biconex.out");

const int dim = 100002;

int n, m;
vector <int> v[dim];
vector < vector <int> > cb;
stack < pair <int, int> > elemCB;

int low[dim], timeDiscovered[dim], parent[dim];
bool mark[dim];

void saveCB(int nodeS, int nodeF){
    vector <int> elem;
    int cx = 0, cy = 0;

    while(elemCB.size() > 0 && !(cx == nodeS && cy == nodeF)){
        cx = elemCB.top().first; elem.push_back(cx);
        cy = elemCB.top().second; elem.push_back(cy);
        elemCB.pop();
    }

    cb.push_back(elem);
}

void DFS(int nod, int time){
    mark[nod] = 1;
    low[nod] = timeDiscovered[nod] = ++time;

    for(auto it: v[nod]){
        if(!mark[it]){
            elemCB.push({nod, it});
            parent[it] = nod;
            DFS(it, time);

            low[nod] = min(low[it], low[nod]);

            if(low[it] >= timeDiscovered[nod])
                saveCB(nod, it);
        } else if(it != parent[nod]){
            low[nod] = min(low[nod], timeDiscovered[it]);
        }
    }
}

int main()
{
    int i, a, b;

    f >> n >> m;

    for(i = 1; i <= m; ++i){
        f >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    DFS(1, 0);

    g << cb.size() << '\n';

    for(auto it: cb){
        sort(it.begin(), it.end());
        it.erase(unique(it.begin(), it.end()), it.end());
        for(auto ind: it)
            g << ind << " ";
        g << '\n';
    }

    return 0;
}