Cod sursa(job #896991)

Utilizator Eugen01Vasilescu Eugen Eugen01 Data 27 februarie 2013 18:22:46
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include<fstream>
#include<vector>
#include<cstring>
#include<algorithm>
#define pb push_back
#define mp make_pair
#define Nmax 100009

using namespace std;

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

int j,nr,n,m,i,x,y,L[Nmax],T[Nmax],nivel[Nmax],ok[Nmax];
vector<int> a[Nmax],sol[Nmax];
vector<pair<int,int> >Q;

void DF(int nod)
{
    vector<int>::iterator it;
    int nod2;

    ok[nod]=1;

    for (it=a[nod].begin();it!=a[nod].end();it++)
    {
        nod2=*it;
        if (!ok[nod2])
        {
            Q.pb(mp(nod,nod2));
            nivel[nod2]=nivel[nod]+1;
            T[nod2]=nod;
            DF(nod2);
            L[nod]=min(L[nod],L[nod2]);
        }
        else
            L[nod]=min(L[nod],nivel[nod2]);
    }
    if (L[nod] >= nivel[T[nod]] && nod!=1)
    {
        nr++;
        while (Q.back().first!=T[nod] || Q.back().second!=nod)
        {
            sol[nr].pb(Q.back().first);
            sol[nr].pb(Q.back().second);
            Q.pop_back();
        }
        Q.pop_back();
        sol[nr].pb(nod);
        sol[nr].pb(T[nod]);
    }
}

int main()
{
    in>>n>>m;
    for (i=1;i<=m;i++)
    {
        in>>x>>y;
        a[x].pb(y);
        a[y].pb(x);
    }
    memset(L,0x3f3f3f3f,sizeof(L));
    nivel[1]=1;
    DF(1);

    out<<nr<<'\n';
    for (i=1;i<=nr;i++)
    {
        sort(sol[i].begin(),sol[i].end());
        out<<sol[i][0]<<' ';
        for (j=1;j<sol[i].size();j++)
            if (sol[i][j]!=sol[i][j-1])
                out<<sol[i][j]<<' ';
        out<<'\n';
    }
}