Cod sursa(job #1889453)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 22 februarie 2017 18:46:24
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

int i, j, n, m, x, y, c,niv[100005],lmax[100005];
stack<int> stiva;
vector<int>sl,ls[100005];
vector<vector<int> >sol;
int viz[100005];

void add(int x, int tt) {
    sl.clear();
    sl.push_back(tt);
    //g<<x << ' ' << tt << '\n';
    while (stiva.empty()==0&&(c=stiva.top()) != x) {
        sl.push_back(c);
        stiva.pop();
    }
    sl.push_back(x);
    if (stiva.empty()==0)
        stiva.pop();
    sol.push_back(sl);
}

void df(int x, int tt) {
    int i, y, l = ls[x].size();
    niv[x] =lmax[x] = niv[tt]+1;
    viz[x] = 1;
    for (i = 0; i < l; i++) {
        y = ls[x][i];
        if (y == tt)
            continue;
        if (viz[y] == 1) {
            lmax[x] = min(lmax[x], niv[y]);
            continue;
        }
        viz[y] = 1;
        stiva.push(y);
        df(y,x);
        lmax[x] = min(lmax[x], lmax[y]);
        if (lmax[y] >= niv[x])
            add(y,x);
    }
    //g <<x <<  ' ';
}

int main() {
    f >> n >> m;
    while (m--) {
        f >> x >> y;
        ls[x].push_back(y);
        ls[y].push_back(x);
        //g << x << ' ' << y << '\n';
    }
    for (i = 1; i <= n; i++)
        if (viz[i] == 0)
            df(i,0);

    g << (c = sol.size()) << '\n';
    for (i = 0; i < c; i++) {
        x = sol[i].size();
        for (j = 0; j < x; j++)
            g << sol[i][j] <<' ';
        g << '\n';
    }
    return 0;
}