Cod sursa(job #2410506)

Utilizator aditzu7Adrian Capraru aditzu7 Data 20 aprilie 2019 09:28:10
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
int nnnn,i,x,y,nn,ssol,n,m,d[100005],low[100005],t[100005],sol[100005];
struct nod
{
    int inf;
    nod *urm;


} *l[100005];
struct stiva{
int x;
int y;
} st[200005];
void adaug(nod *&u,int x){
nod *p;
p=new nod;
p->inf=x;
p->urm=u;
u=p;

}
void df(int x){
int i;
low[x]=d[x];
for(nod *j=l[x];j;j=j->urm){
    int inf=j->inf;
    if(!d[inf]){
        d[inf]=d[x]+1;
        t[inf]=x;
        df(inf);
        low[x]=min(low[x],low[inf]);
        if(low[inf]>=d[x]) ssol++;

    }
    else if (inf!=t[x]) low[x]=min(low[x],d[inf]);
}


}
void df2(int x){
int i;
low[x]=d[x];
for(nod *j=l[x];j;j=j->urm){
    int inf=j->inf;
    if(inf!=t[x]&&d[inf]<d[x]) st[++nn].x=inf,st[nn].y=x;
    if(!d[inf]){
        d[inf]=d[x]+1;
        t[inf]=x;
        df2(inf);
        low[x]=min(low[x],low[inf]);
        if(low[inf]>=d[x]) {
                 nnnn=0;
int a,b;
        do{

        a=st[nn].x;
        b=st[nn].y;
            sol[++nnnn]=st[nn].x;
            sol[++nnnn]=st[nn].y;
            nn--;

        } while(nn>0&&!(a==inf&&b==x||a==x&&b==inf));
        sort(sol+1,sol+nnnn+1);
        for(int j1=1;j1<=nnnn;j1++)
            if(sol[j1]!=sol[j1-1]) printf("%d ",sol[j1]);
        printf("\n");


        }

    }
    else if (inf!=t[x]) low[x]=min(low[x],d[inf]);
}


}
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);
        adaug(l[x],y);
        adaug(l[y],x);

    }
    df(1);
    for(i=1;i<=n;i++) d[i]=low[i]=t[i]=0;
    printf("%d\n",ssol);
    d[1]=1;
    df2(1);
    return 0;
}