Cod sursa(job #1166174)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 3 aprilie 2014 12:22:19
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include<fstream>
#include<utility>
#include<stack>
#include<set>
#include<vector>
#define NMAX 100010
#define f first
#define s second

using namespace std;

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

vector<int> a[NMAX];
set<int> comp[NMAX];
stack< pair<int, int> > stiva;
int n, m, nr=0, vz[NMAX], t[NMAX], niv[NMAX], sus[NMAX];

void Citeste()
{
    int x, y;

    f>>n>>m;
    while (m--)
    {
        f>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
}

void Extrage(int x, int y)
{
    pair<int, int> pr;

    ++nr;
    do
    {
        pr=stiva.top(); stiva.pop();
        comp[nr].insert(pr.f);
        comp[nr].insert(pr.s);
    }while ((pr.f!=x || pr.s!=y) && (pr.s!=x || pr.f!=y));
}
void DFS(int nod)
{
    vector<int> :: iterator it;

    vz[nod]=1;
    for (it=a[nod].begin(); it!=a[nod].end(); ++it)
        if (vz[*it]) sus[nod]=min(sus[nod], niv[*it]);
        else
        {
            stiva.push(make_pair(nod, *it));
            sus[*it]=niv[*it]=niv[nod]+1; t[*it]=nod;
            DFS(*it);
            sus[nod]=min(sus[nod], sus[*it]);

            if (sus[*it]>=niv[nod]) Extrage(nod, *it);
        }
}

void Solve()
{
    int i;

    for (i=1; i<=n; ++i)
        if (!vz[i])
        {
            t[i]=-1; niv[i]=1;
            DFS(i);
        }
}

void Scrie()
{
    int i;
    set<int> :: iterator is;
    g<<nr<<"\n";
    for (i=1; i<=nr; ++i)
    {
        for (is=comp[i].begin(); is!=comp[i].end(); ++is) g<<(*is)<<" ";
        g<<"\n";
    }
}

int main()
{
    Citeste();

    Solve();

    Scrie();

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