Cod sursa(job #2378419)

Utilizator EricEric Vilcu Eric Data 12 martie 2019 10:59:18
Problema Componente biconexe Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m,k,num;
int v[100001];
int stk[200002][2];
struct mc{int d;mc*n;}*a[100001];
struct vmc{vmc*n;mc*m;}*K;
void dstk(int i,int j)
{
    vmc*t=new vmc;t->m=NULL;t->n=K;K=t;
    while(stk[k][0]!=i&&stk[k][1]!=j)
    {
        --k;
        mc*t2=new mc;t2->n=t->m;t->m=t2;
        t2->d=stk[k][0];
           t2=new mc;t2->n=t->m;t->m=t2;
        t2->d=stk[k][1];
    }
    ++num;
}
int dfsl(int i,int ld,int d,int o)
{
    v[i]=d;
    for(mc*l=a[i];l!=NULL;l=l->n)
    {
        int j=l->d;
        if(j!=o)
        {
            if(0==v[j])
            {stk[k][0]=i;stk[k][1]=j;++k;
                int ma=dfsl(j,d+1,d+1,i);
                if(ma<ld)ld=ma;
                else
                {
                    dstk(i,j);
                }
            }
            else ld=min(ld,v[j]);
        }
    }
    return ld;
}
int main()
{
    f>>n>>m;K=NULL;
    for(int i=1;i<=n;++i)a[i]=NULL;
    for(int i=1;i<=m;++i){int x,y;f>>x>>y;
        mc*l=new mc;l->d=x;l->n=a[y];a[y]=l;
           l=new mc;l->d=y;l->n=a[x];a[x]=l;
    }
    dfsl(1,1,1,1);
    for(int i=1;i<=n;++i)v[i]=0;k=1;
    g<<num<<'\n';
    for(vmc*q=K;q!=NULL;q=q->n)
    {
        for(mc*t=q->m;t!=NULL;t=t->n)if(v[t->d]!=k)
            {v[t->d]=k;g<<t->d<<' ';}
        g<<'\n';++k;
    }
}