Cod sursa(job #1851336)

Utilizator ASTELOTudor Enescu ASTELO Data 19 ianuarie 2017 17:17:14
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include<cstdio>
#include<vector>
using namespace std;
struct eu{int x,y;};
eu st[200001];
vector<int> v[100001],v1[100001];
int cate,i,n,j,m,nr,cate2,pc,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++;
    while(x!=q1&&y!=q2)
        {
        v1[cate2].push_back(q1);
        v1[cate2].push_back(q2);
        q1=st[cate].x;
        q2=st[cate].y;
        cate--;
        }
    v1[cate2].push_back(q1);
    v1[cate2].push_back(q2);
    }
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];
            }
        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);
                }
            }
        }
    }
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;
        vc[++cc]=i;
        nr=0;
        dfs(i);
        if(nr>=2)
            marc[i]=1;
        else
            marc[i]=0;
        }
printf("%d\n",cate2);
for(i=1;i<=cate2;i++)
    {
    for(j=v1[i].size()-1;j>=0;j-=2)
        printf("%d ",v1[i][j]);
    printf("%d\n",v1[i][v1[i].size()-2]);
    }
return 0;
}