Cod sursa(job #731685)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 8 aprilie 2012 21:37:55
Problema Componente biconexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 2.16 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>

#define NMax 50000
#define x first
#define y second

using namespace std;

vector <int> G[NMax], T[NMax], CV;
vector < vector <int> > BC;
int N, S, E, Q;
int Level[NMax], MinLevel[NMax];
stack < pair <int, int> > Edges;

inline void DetBC (int X, int Y)
{
    vector <int> Component;
    int NewX, NewY;
    do
    {
        NewX=Edges.top ().x, NewY=Edges.top ().y;
        Edges.pop ();
        Component.push_back (NewX); Component.push_back (NewY);
    }
    while (NewX!=X or NewY!=Y);
    sort (Component.begin (), Component.end ());
    Component.erase (unique (Component.begin (), Component.end ()), Component.end ());
    BC.push_back (Component);
}

inline void ComponentDFS (int X, int Father, int L)
{
    Level[X]=MinLevel[X]=L;
    int NSons=0; bool Critical=false;
    for (vector <int> :: iterator Y=G[X].begin (); Y!=G[X].end (); ++Y)
    {
        if (*Y==Father) continue;
        if (!Level[*Y])
        {
            ++NSons; Edges.push (make_pair (X, *Y));
            ComponentDFS (*Y, X, L+1);
            if (MinLevel[*Y]>=Level[X])
            {
                Critical=true; DetBC (X, *Y);
            }
        }
        MinLevel[X]=min (MinLevel[X], MinLevel[*Y]);
    }
    if (X==Father and NSons>1) Critical=true;
    if (Critical) CV.push_back (X);
}

void BuildBC ()
{
    for (int i=1; i<=N; ++i)
    {
        if (!Level[i]) ComponentDFS (i, i, 1);
    }
}

void Solve ()
{
    BuildBC ();
}

void Read ()
{
    freopen ("biconex.in", "r", stdin);
    int M; scanf ("%d %d", &N, &M);
    for (; M>0; --M)
    {
        int X, Y; scanf ("%d %d", &X, &Y);
        G[X].push_back (Y); G[Y].push_back (X);
    }
    scanf ("%d %d %d", &S, &E, &Q);
}

void Print ()
{
    freopen ("biconex.out", "w", stdout);
    printf ("%d\n", (int)BC.size ());
    for (int i=0; i<(int)BC.size (); ++i)
    {
        for (int j=0; j<(int)BC[i].size (); ++j)
        {
            printf ("%d ", BC[i][j]);
        }
        printf ("\n");
    }
}

int main()
{
    Read ();
    Solve ();
    Print ();
    return 0;
}