Cod sursa(job #1142864)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 14 martie 2014 12:30:24
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include<fstream>
#include<vector>
#include<stack>
#include<utility>
#define NMAX 200010
#define f first
#define s second

using namespace std;

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

vector<int> a[NMAX], comp[NMAX];
stack<pair<int, int> > s;
int n, m, nrcomp, rad, nrad, t[NMAX], niv[NMAX], sus[NMAX], vz[NMAX];


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

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

void Extrage(int x, int y)
{
    pair<int, int> pr;
    ++nrcomp;
    do
    {
        pr=s.top();
        if (x!=pr.f)
        {
            comp[nrcomp].push_back(pr.s);
            s.pop();
        }
        else comp[nrcomp].push_back(pr.s);
    }while (x!=pr.f && y!=pr.s);
}

void DFS(int nod)
{
    int i, fiu;

    vz[nod]=1;

    for (i=0; i<a[nod].size(); ++i)
    {
        fiu=a[nod][i];

        if (vz[fiu]) sus[nod]=min(sus[nod], niv[fiu]);
        else
        {
            t[fiu]=nod; niv[fiu]=niv[nod]+1; sus[fiu]=niv[fiu]; s.push(make_pair(nod, fiu));
            DFS(fiu);
            sus[nod]=min(sus[nod], sus[fiu]);
            if (sus[fiu]>=niv[t[fiu]])
                Extrage(t[nod], nod);
        }
    }
}

void Solve()
{
    int i;

    for (i=1; i<=n; ++i)
        if (!vz[i])
        {
            t[i]=-1; niv[i]=1; sus[i]=1; s.push(make_pair(-1, 1));
            DFS(i);
        }
}

void Scrie()
{
    int i, j;
    g<<nrcomp<<"\n";
    for (i=1; i<=nrcomp; ++i)
    {
        for (j=0; j<comp[i].size(); ++j) g<<comp[i][j]<<" ";
        g<<"\n";
    }
}

int main()
{
    Citeste();

    Solve();

    Scrie();

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