Cod sursa(job #1143107)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 14 martie 2014 19:10:08
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include<fstream>
#include<iostream>
#include<stack>
#include<vector>
#include<set>
#include<utility>
#define NMAX 100010
#define f first
#define s second

using namespace std;

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

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

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

    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=s.top(); s.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)
{
    int i, fiu;

    sus[nod]=niv[nod]; 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
        {
            s.push(make_pair(nod, fiu)); niv[fiu]=niv[nod]+1; t[fiu]=nod;

            DFS(fiu);

            sus[nod]=min(sus[nod], sus[fiu]);

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

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;
}