Cod sursa(job #1756040)

Utilizator Theodor1000Cristea Theodor Stefan Theodor1000 Data 11 septembrie 2016 18:14:36
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <cstdio>
#include <algorithm>
#include <vector>

#define pii pair <int, int>
#define f first
#define s second

using namespace std;

vector <int> v[100010], rez[100010];
bool ap[100010];
int st[200010];
int k = 0, nr = 0, niv[100010], low[100010];

inline void dfs (int nod, int tata)
{
    ap[nod] = true;
    low[nod] = niv[nod] = niv[tata] + 1;

    for (auto &it : v[nod])
        if (ap[it] && it != tata)
            low[nod] = min (low[nod], low[it]);

        else if (!ap[it])
        {
            st[++k] = it;
            dfs (it, nod);

            low[nod] = min (low[nod], low[it]);
            if (low[it] >= niv[nod])
            {
                ++nr;
                while (st[k] != it)
                    rez[nr].push_back (st[k--]);

                --k;
                rez[nr].push_back (nod);
                rez[nr].push_back (it);
            }
        }
}

int main ()
{
    freopen ("biconex.in", "r", stdin);
    freopen ("biconex.out", "w", stdout);

    int n, m;
    scanf ("%d %d", &n, &m);

    for (int i = 1; i <= m; ++i)
    {
        int x, y;
        scanf ("%d %d", &x, &y);

        v[x].push_back (y);
        v[y].push_back (x);
    }

    st[++k] = 1;
    dfs (1, 0);
    printf ("%d\n", nr);

    for (int i = 1; i <= nr; ++i, printf ("\n"))
        for (auto &it : rez[i])
            printf ("%d ", it);

    return 0;
}