Cod sursa(job #933406)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 29 martie 2013 22:41:08
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <cstdio>
#include <vector>
#include <stack>
#define MAX_N 100010

using namespace std;

stack <int> s;
vector <int> g[MAX_N], sol[MAX_N];
int n, m, cnt, lev[MAX_N], levacc[MAX_N], u[MAX_N];

void df(int nod, int t) {
    int i, v;
    u[nod] = 1;
    s.push(nod);
    for (i = 0; i < g[nod].size(); i++) {
        v = g[nod][i];
        if (v == t) continue;
        if (u[v]) {
            levacc[nod] = min (levacc[nod], lev[v]);
            continue;
        }
        lev[v] = levacc[v] = lev[nod] + 1;
        df(v, nod);
        if (levacc[v] >= lev[nod]) {
            cnt++;
            while (s.top() != nod && !s.empty()) {
                sol[cnt].push_back (s.top());
                s.pop();
            }
            sol[cnt].push_back (s.top());
        }
        levacc[nod] = min (levacc[nod], levacc[v]);
    }
}

int main()
{
    freopen ("biconex.in","r",stdin);
    freopen ("biconex.out","w",stdout);
    scanf ("%d %d", &n, &m);
    int i, x, y;
    for (i = 1; i <= m; i++) {
        scanf ("%d %d", &x, &y);
        g[x].push_back (y);
        g[y].push_back (x);
    }
    df(1, 0);
    printf ("%d\n", cnt);
    for (i = 1; i <= cnt; i++) {
        for (int j = 0; j < sol[i].size(); j++) printf ("%d ",sol[i][j]);
        printf("\n");
    }
    return 0;
}