Cod sursa(job #1858321)

Utilizator raduzxstefanescu radu raduzx Data 27 ianuarie 2017 13:43:35
Problema Componente biconexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.43 kb
#include <fstream>

using namespace std;
struct eu{int x,y;};
eu st[100001];
ifstream f("biconex.in");
ofstream g("biconex.out");
struct nod
{
    int val;
    nod *urm;
};
typedef nod *pnod;
pnod p,v[100003],v2[100003];
void ad(int x,int y)
{
    p=new nod;
    p->val=y;
    p->urm=v[x]->urm;
    v[x]->urm=p;
}
pnod t,r;
void adaug(int x,int y)
{
    t=v2[y];
    p=t->urm;
    while(p and p->val<x)
    {
        t=p;
        p=p->urm;
    }
    if(p)
    {
        r=new nod;
        r->val=x;
        r->urm=p;
        t->urm=r;
    }
    else
    {
        r=new nod;
        r->val=x;
        r->urm=0;
        t->urm=r;
    }
}
int cate,i,n,j,m,nr,cate2,viz[100001],niv[100001],l[100001],marc[100001],tata[1000001],vc[100001],x,y,rad,cc;
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;
    while(x!=q1&&y!=q2)
        {
        adaug(q2,cate2);
      //  adaug(q1,cate2);
        q1=st[cate].x;
        q2=st[cate].y;
        cate--;
        }
   adaug(q1,cate2);
  adaug(q2,cate2);
    }
void dfs(int nod)
    {
    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;
}