Cod sursa(job #1411150)

Utilizator geniucosOncescu Costin geniucos Data 31 martie 2015 14:41:29
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.98 kb
#include<algorithm>
#include<cstdio>
#include<vector>
#include<stack>

using namespace std;

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

vector < int > v[100009];
vector < vector < int > > answer;
stack < pair < int , int > > S;

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 > stop)
{
    vector < int > comp;
    pair < int , int > top;
    do
    {
        top = S.top ();
        S.pop ();
        comp.push_back (top.first);
        comp.push_back (top.second);
    }while (top != stop);

    unific (comp);
    answer.push_back (comp);
}

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)
        {
            niv[*it] = niv[nod] + 1;
            S.push (make_pair (nod, *it));

            dfs (*it, nod);

            if (dp[*it] > niv[nod])
                ;////muchie critica

            if (dp[*it] >= niv[nod])
                Add_Component (make_pair (nod, *it));////nod e critic
        }

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

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

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

scanf ("%d %d", &N, &M);
while (M)
{
    M --;
    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;

dfs (1, 0);
Print ();

return 0;
}