Cod sursa(job #1409796)

Utilizator 4ONI2015oni2015 4ONI2015 Data 30 martie 2015 18:36:20
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>
#define pb push_back
#define N 100005

using namespace std;
vector<int>v[N], cb[N], q;
int sol, low[N], niv[N], cnt, n, m, x, y, i;
void get_sol(int x, int y)
{
    sol++;
    while(y != q.back())
    {
        cb[sol].pb(q.back());
        q.pop_back();
    }
    q.pop_back();
    cb[sol].pb(y);
    cb[sol].pb(x);
}
void df(int nod, int tata)
{
    niv[nod] = low[nod] = ++cnt;
    for(auto it : v[nod])
    {
        if(it == tata)
            continue;
        if(niv[it])
        {
            low[nod] = min(low[nod], niv[it]);
            continue;
        }
        q.pb(it);
        df(it, nod);
        low[nod] = min(low[nod], low[it]);
        if(low[it] >= niv[nod])
            get_sol(nod, it);
    }

}
int main()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(; m; m--)
    {
        scanf("%d%d", &x, &y);
        v[x].pb(y);
        v[y].pb(x);
    }
    df(1, 0);
    printf("%d\n", sol);
    for(i = 1; i <= sol; i++)
    {
        for(auto it : cb[i])
            printf("%d ", it);
        printf("\n");
    }
    return 0;
}