Cod sursa(job #1863675)

Utilizator c909073Petrisor Addrian c909073 Data 31 ianuarie 2017 09:09:28
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.7 kb
#include <fstream>

using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int p,n,m,ok;
int nivel[100005],l[100005],tata[100005],a[100005];
struct muchie
{
    int i,j;

}st[300005];
int u =0;
struct nod
{
    int info;
    nod*urm;
}*pt[100005];
struct comp
{
    nod *q;
    comp *next;
}*elemx;
int k;
void inserarenod(nod *&point,int val)
{
    nod *cap=new nod;
    cap->info=val;
    cap->urm=point;
    point=cap;
}
void inserarecomp(comp *&point)
{
    comp *cap=new comp;
    cap->q=NULL;
    cap->next=point;
    point= cap;
}
void Afisarenod(nod *&point)
{
    nod *cap=point;
    while(cap!=NULL)
    {
        g<<cap->info<<" ";
        cap=cap->urm;
    }

}
void Afisarecomp(comp *& point)
{
    comp *cap=point;
    while(cap!=NULL)
    {
        Afisarenod(cap->q);
        g<<'\n';
        cap=cap->next;
    }
}
void  drum(int xp)
{
    while(l[tata[xp]]>l[xp])
    {
        l[tata[xp]]= l[xp];
        xp=tata[xp];
    }
}
void compbiconex(int x, int y)
{
    int ct=0, verif=0;
    k++;
    inserarecomp(elemx);
    while(verif==0)
    {
        if(a[st[u].i]!=k)
        {
            ct++;
            a[st[u].i]=k;
            inserarenod(elemx->q,st[u].i);
        }
        if(a[st[u].j]!=k)
        {
            ct++;
            a[st[u].j]=k;
            inserarenod(elemx->q,st[u].j);
        }
        if(st[u].i== x && st[u].j==y)
            verif =1;
        st[u].i=st[u].j=0;
        u--;
    }
}
void df2(int xp, int r)
{
    nod *cap=pt[xp];
    int y;
    while(cap!=NULL)
    {
        y=cap->info;
        if(y!=tata[xp])
        {
            if(nivel[y]!=0 && nivel[y]<nivel[xp])
            {
                if(l[xp]>nivel[y])
                {
                    l[xp]=nivel[y];
                    drum(xp);
                }
                u++;
                st[u].i=xp;
                st[u].j=y;
            }
            else
                if(nivel[y]==0)
            {
                nivel[y]=nivel[xp]+1;
                l[y]=nivel[y];
                tata[y]=xp;
                u++;
                st[u].i=xp;
                st[u].j=y;
                df2(y,r);
                if(l[y]>=nivel[xp])
                    compbiconex(xp,y);
            }
        }
        cap=cap->urm;
    }
}
int main()
{
    int a,b,r;
    f>>n>>m;
    for(int i=1;i<=n;i++)
        pt[i]=NULL;
    elemx=NULL;
    for(int i=1;i<=m;i++)
    {
        f>>a>>b;
        inserarenod(pt[a],b);
        inserarenod(pt[b],a);
    }
    r=1;
    tata[r]=0;
    nivel[r]=1;
    l[r]=1;
    df2(r,r);
    g<<k<<'\n';
    Afisarecomp(elemx);
    return 0;
}