Cod sursa(job #1300427)

Utilizator geniucosOncescu Costin geniucos Data 24 decembrie 2014 14:07:20
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.15 kb
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>

using namespace std;

int N, M, dp[100009], niv[100009];

vector < int > v[100009];
vector < vector < int > > componente;
stack < pair < int , int > > stiva_muchii;

void unific ( vector < int > &v)
{
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
}

void Add_Component (pair < int, int > end)
{
    pair < int , int > top;
    vector < int > componenta;
    do
    {
        top = stiva_muchii.top();
        stiva_muchii.pop();
        componenta.push_back (top.first);
        componenta.push_back (top.second);
    }while (top != end);
    unific (componenta);
    componente.push_back (componenta);
}

void dfs (int nod, int tata)
{
    dp[nod] = niv[nod];
    for (vector < int > :: iterator it = v[nod].begin(); it != v[nod].end(); it++)
    {
        if (niv[*it] != -1)
            continue;
        niv[*it] = niv[nod] + 1;
        stiva_muchii.push (make_pair (nod, *it));
        dfs (*it, nod);
        if (dp[*it] > niv[nod])
            ;/////muchie critica de la *it la nod
        if (dp[*it] >= niv[nod])
            Add_Component (make_pair (nod, *it));/////nod este nod critic
    }

    bool consumat = 0;
    for (vector < int > :: iterator it = v[nod].begin(); it != v[nod].end(); it++)
    {
        if (consumat == 0 && *it == tata)
            consumat = 1;
        else
            dp[nod] = min (dp[nod], dp[*it]);
    }
}

void afis ()
{
    printf ("%d\n", componente.size());
    for (int i=0; i<componente.size(); i++, printf ("\n"))
        for (vector < int > :: iterator it = componente[i].begin(); it != componente[i].end(); it++)
            printf ("%d ", *it);
}

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

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);
}

for (int i=1; i<=N; i++)
    niv[i] = -1;

for (int i=1; i<=N; i++)
    if (niv[i] == -1)
    {
        niv[i] = 0;
        dfs (i, 0);
    }

afis ();

return 0;
}