Cod sursa(job #1863683)

Utilizator c909073Petrisor Addrian c909073 Data 31 ianuarie 2017 09:20:35
Problema Componente biconexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.73 kb
//Problema1

#include <fstream>

using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
struct nod
{
    int val;
    nod *urm;
};
typedef nod *pnod;
pnod v[100003],p,v2[100003],ultim;
int viz[100003];
int cate,i,n,j,m,nr,cate2,pc,niv[100003],l[100003],marc[100003],tata[100003],vc[100003],x,y,rad,cc;
void ad(int x,int y)
{
    p=new nod;
    p->val=y;
    p->urm=v[x]->urm;
    v[x]->urm=p;
}
int index,ss;
struct acum
{
    int x,y;
};
acum st[200002];
pnod rt;
int op;
pnod t,rty;
void adaug(int a,int e)
{
    t=v2[e];
    p=v2[e]->urm;
    while(p and p->val<a)
    {
        t=p;
        p=p->urm;
    }
    if(p)
    {
        rty=new nod;
        rty->val=a;
        rty->urm=p;
        t->urm=rty;
    }
    else
    {
        rty=new nod;
        rty->val=a;
        rty->urm=0;
        t->urm=rty;
    }
}
void pas(int x,int y)
{
    int q1=st[cate].x,q2=st[cate].y;
    cate--;
    cate2++;
    v2[cate2]=new nod;
    v2[cate2]->urm=0;
    ultim=v2[cate2];
    while(x!=q1 and y!=q2)
    {
       /* rt=new nod;
        rt->val=q1;
        rt->urm=v2[cate2]->urm;
        v2[cate2]->urm=rt;*/
        adaug(q2,cate2);
        q1=st[cate].x;
        q2=st[cate].y;
        cate--;
    }
    adaug(q2,cate2);
    adaug(q1,cate2);
    //v2[cate2]->urm=rt;
}
void dfs(int nod)
{
    int i;
    pnod p;
    viz[nod]=1;
    l[nod]=niv[nod];
    p=v[nod]->urm;
    while(p)
    {
        int f=p->val;
        if(viz[f]==1)
        {
            if(f!=tata[nod] and l[nod]>niv[f])
                l[nod]=niv[f];
        }
        else
        {
            st[++cate].x=nod;
            st[cate].y=f;
            if(nod==rad)
                nr++;
            niv[f]=niv[nod]+1;
            tata[f]=nod;
            dfs(f);
            if(l[nod]>l[f])
                l[nod]=l[f];
            if(l[f]>=niv[nod])
            {
                marc[nod]=1;
                pas(nod,f);
            }
        }
        p=p->urm;
    }
}
int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        v[i]=new nod;
        v[i]->urm=0;
    }
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        ad(x,y);
        ad(y,x);
    }
    for(i=1;i<=n;i++)
    {
        if(viz[i]==0)
        {
            rad=i;
            niv[i]=1;
            cc++;
            vc[cc]=i;
            nr=0;
            dfs(i);
            if(nr>=2)
                marc[i]=1;
            else
                marc[i]=0;
        }
    }
    g<<cate2<<'\n';
    for(i=1;i<=cate2;i++)
    {
        p=v2[i]->urm;
        while(p)
        {
            g<<p->val<<" ";
            p=p->urm;
        }
        g<<'\n';
    }
    return 0;
}