Cod sursa(job #1715355)

Utilizator geo_furduifurdui geo geo_furdui Data 10 iunie 2016 13:58:34
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include <fstream>

using namespace std;
ifstream cin ("biconex.in");
ofstream cout ("biconex.out");
int t[2][400001],start[100001],v[100001],n,m,l[100001],niv[100001],k,q,tata[100001],used[100001],nr1,radacina,st[2][100001],vf,sol[200001],p;
void citire ()
{
    cin>>n>>m; int x,y;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        t[0][++k]=y; t[1][k]=start[x]; start[x]=k;
        t[0][++k]=x; t[1][k]=start[y]; start[y]=k;
    }
}
void add (int x,int y)
{
    st[1][++vf]=y;
    st[0][vf]=x;
}
void scoate (int x,int y)
{
    while(3>2 && vf>0)
    {
        if((st[0][vf]==x && st[1][vf]==y) || (st[0][vf]==y && st[1][vf]==x)) break;
        sol[++p]=st[1][vf]; vf--;
    }  sol[++p]=st[1][vf]; sol[++p]=st[0][vf]; vf--;
    q++; sol[++p]=-1;
}
void dfs (int nod)
{
    used[nod]=1;
    l[nod]=niv[nod];
    int p=start[nod];
    while(p)
    {
        if(t[0][p]!=tata[nod] && niv[nod]>niv[t[0][p]])
            add(nod,t[0][p]);
       if(used[t[0][p]]==0)
       {
           niv[t[0][p]]=niv[nod]+1;
           tata[t[0][p]]=nod;
           if(radacina==nod) nr1++;
           dfs(t[0][p]);
           if(l[t[0][p]]<l[nod]) l[nod]=l[t[0][p]];
           if(l[t[0][p]]>=niv[nod])
              scoate(t[0][p],nod);
       }
       else if( tata[nod]!=t[0][p] && niv[t[0][p]]<l[nod]) l[nod]=niv[t[0][p]];
       p=t[1][p];
    }
}
void parcurg ()
{
    niv[1]=1;
    dfs(1);
}
void scrie ()
{ int k=1,care=1,y=0;
    cout<<q<<"\n";
    while(y<q)
    {
        if(sol[k]==-1) {care++; cout<<"\n";y++;}
        else
        if(v[sol[k]]<care)
        {
            v[sol[k]]=care; cout<<sol[k]<<" ";
        } ++k;
    }
}
int main()
{
    citire();
    parcurg();
    scrie();
    return 0;
}