Cod sursa(job #928997)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 26 martie 2013 19:51:18
Problema Componente biconexe Scor 52
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include<fstream>
#include<vector>
#include<utility>
#include<stack>
#define f first
#define s second
#define NMAX 100010

using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

int n, m, nr=0, comp=1, ns=0, dfn[NMAX], low[NMAX];

vector<int> v[NMAX], a[NMAX];
stack<pair <int, int> > S;

void Citeste()
{
    int i, x, y;

    f>>n>>m;

    for (i=1; i<=m; ++i)
    {
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
}

void Scoate(int x, int nod)
{
    pair< int, int > pr;
    int nr=0;

    do
    {
        pr=S.top(); S.pop(); ++nr;
        a[comp].push_back(pr.s);

    }while (pr.s!=nod || pr.f!=x);

   if (nr==1) a[comp].push_back(pr.f);

    ++comp;
}

void Biconex(int nod, int tata)
{
    int i, x;

    dfn[nod]=low[nod]=++nr;

    for (i=0; i<v[nod].size(); ++i)
    {
        x=v[nod][i];

        if (x!=tata && dfn[x]<dfn[nod])
        {
            S.push( make_pair(x, nod) );
        }

        if (!dfn[x])
        {
            Biconex(x, nod);

            low[nod]=min(low[nod], low[x]);

            if (low[x]>=dfn[nod])
                Scoate(x, nod);
        }
        else
            if (x!=tata) low[nod]=min(low[nod], dfn[x]);

    }
}

void Scrie()
{
    int i, j;

    g<<comp-1<<"\n";

    for (i=1; i<comp; ++i)
    {
        for (j=0; j<a[i].size(); ++j) g<<a[i][j]<<" ";
        g<<"\n";
    }
}


int main()
{
    Citeste();

    Biconex(1, -1);

    Scrie();

    f.close();
    g.close();
    return 0;
}