Cod sursa(job #906900)

Utilizator valentina506Moraru Valentina valentina506 Data 7 martie 2013 13:03:42
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<fstream>
#include<vector>
using namespace std;
int n,m,i,j,st1[200001],st2[200001],niv[200001],c[200001],nr,x,y,u;
vector<int>a[200001],sol[200001];
bool uz[200001];
void add(int a, int b)
{
    int x,y;
    nr++;
    do
    {
        x=st1[u];
        y=st2[u--];
        sol[nr].push_back(y);
    }while(x!=a||y!=b);
    sol[nr].push_back(x);
}
void df(int nod,int tata)
{
    int i,x;
    niv[nod]=niv[tata]+1;
    c[nod]=niv[nod];
    uz[nod]=1;
    for(i=0;i<a[nod].size();++i)
    {
        x=a[nod][i];
        if(!uz[x])
        {
            st1[++u]=nod;
            st2[u]=x;
            df(x,nod);
            if(c[x]<c[nod])
              c[nod]=c[x];
            if(c[x]>=niv[nod])
              add(nod,x);
        }
        else if(x!=tata&&c[x]<c[nod])
           c[nod]=c[x];
    }
}

int main()
{
    ifstream f("biconex.in");
    ofstream g("biconex.out");
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    nr=u=0;
    df(1,0);
    g<<nr<<"\n";
    for(i=1;i<=nr;++i)
    {
        for(j=0;j<sol[i].size();++j)
        g<<sol[i][j]<<" ";
        g<<"\n";
    }
    return 0;
}