Cod sursa(job #1894303)

Utilizator leonard.david42Bereholschi Leonard David leonard.david42 Data 26 februarie 2017 18:50:57
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 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;
}