Cod sursa(job #1847075)

Utilizator ASTELOTudor Enescu ASTELO Data 14 ianuarie 2017 11:54:26
Problema Componente biconexe Scor 12
Compilator cpp Status done
Runda Arhiva educationala Marime 2.81 kb
#include<cstdio>
#include<vector>
using namespace std;
struct eu{int x,y;};
eu st[200001];
vector<int> v[100001],vcc[200001];
int i,n,j,q1,m,nr,pc,cate,da,viz[100001],niv[100001],l[100001],tata[1000001],x,y,rad,cc;
void dfs(int nod)
    {
    viz[nod]=1;
    l[nod]=niv[nod];
    for(int i=0;i<v[nod].size();i++)
        {
        int f=v[nod][i];
        if(viz[f]==1)
            {
            if(f!=tata[nod]&&l[nod]>niv[f])
                {
                l[nod]=niv[f];
                int ops=cate,hh=0,h=0;
                while(st[ops].y!=nod&&ops>0)
                    {
                    ops--;
                    hh++;
                    }
                if(ops>0)
                    {
                    vcc[q1].push_back(st[ops].y);
                    while(st[ops].x!=f&&ops>0)
                        {
                        vcc[q1].push_back(st[ops].x);
                        ops--;
                        h++;
                        }
                    if(ops>0)
                        {
                        q1++;
                        vcc[q1].push_back(f);
                        ops--;
                        h++;
                        for(int a=1;a<=hh;a++)
                            st[ops+a]=st[ops+h+a];
                        cate-=h;
                        da=f;
                        }
                    }
                }
            }
        else
            {
            if(nod==rad)
                nr++;
            niv[f]=niv[nod]+1;
            st[++cate].x=nod;
            st[cate].y=f;
            while(cate>=2&&st[cate].x!=st[cate-1].y&&st[cate-1].y!=da)
                {
                int kappa=cate-1,l=0;
                while(st[kappa].y!=st[cate].x&&st[kappa].y!=da)
                    {
                    q1++;
                    vcc[q1].push_back(st[kappa].x);
                    vcc[q1].push_back(st[kappa].y);
                    kappa--;
                    l++;
                    }
                st[cate-l]=st[cate];
                cate-=l;
                }
            tata[f]=nod;
            dfs(f);
            if(l[nod]>l[f])
                l[nod]=l[f];
            }
        }
    }
int main ()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
    {
    scanf("%d%d",&x,&y);
    v[x].push_back(y);
    v[y].push_back(x);
    }
for(i=1;i<=n;i++)
    if(viz[i]==0)
        {
        rad=i;
        niv[i]=1;
        nr=0;
        dfs(i);
        }
printf("%d\n",q1+cate);
for(int i=1;i<=q1;i++)
    {
    for(j=0;j<vcc[i].size();j++)
        printf("%d ",vcc[i][j]);
    printf("\n");
    }
for(int i=1;i<=cate;i++)
    {
    printf("%d %d",st[i].x,st[i].y);
    printf("\n");
    }
return 0;
}