Cod sursa(job #2123516)

Utilizator aditzu7Adrian Capraru aditzu7 Data 6 februarie 2018 12:33:12
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.6 kb
#include <stdio.h>
#include <iostream>
using namespace std;
FILE*f=fopen("biconex.in","r");
FILE*g=fopen("biconex.out","w");
int okk,nn=0,st[2][10001],r,nr,t[10001],low[10001],niv[10001],use[10001],nrc,x,y,n,m,i;
struct nod{
int inf;
nod *urm;

}*l[10001];
void adaug(nod *&a,int b){
nod *c;
c=new nod;
c->inf=b;
c->urm=a;
a=c;

}
void push(int a,int b){
    if(a>b){
        int aux=a;
        a=b;
        b=aux;


    }
st[++nn][0]=a;
st[nn][1]=b;

}
void pop(int &a,int &b){
a=st[nn][0];
b=st[nn][1];
  /*if(a>b){
        int aux=a;
        a=b;
        b=aux;


    }*/
nn--;
}
void df(int i){
    int x,y,ki,j;
nod *c;
use[i]=1;
low[i]=niv[i];
for(c=l[i];c;c=c->urm){
        if(c->inf!=t[i]&&niv[i]>niv[c->inf])push(i,c->inf);
 if(!use[c->inf]){
    niv[c->inf]=niv[i]+1;
    t[c->inf]=i;
    //if(i==r)nr++;
    df(c->inf);
    low[i]=min(low[i],low[c->inf]);
    if(low[c->inf]>=niv[i]){int dd=0,ok=0,init=st[nn][0];
        do{dd++;
            pop(x,y);
     if(okk){     if(init==x&&ok!=0) fprintf(g,"%d ",y);
else  {ok=1;fprintf(g,"%d ",x);}}

        }while((x!=i||y!=c->inf)&&(x!=c->inf||y!=i));
       if(okk){ if(dd==1) fprintf(g,"%d ",y);
        fprintf(g,"\n");}
nrc++;


    }

 }
    else if(c->inf!=t[i]) low[i]=min(low[i],niv[c->inf]);

}

}/*
void df2(int i){
    int x,y,ki,j;
nod *c;
use2[i]=1;
low[i]=niv[i];
for(c=l[i];c;c=c->urm){
        if(c->inf!=t[i]&&niv[i]>niv[c->inf])push(i,c->inf);
 if(!use2[c->inf]){
    niv[c->inf]=niv[i]+1;
    t[c->inf]=i;
    //if(i==r)nr++;
    df(c->inf);
    low[i]=min(low[i],low[c->inf]);
    if(low[c->inf]>=niv[i]){int dd=0,ok=0,init=st[nn][0];
        do{dd++;
            pop(x,y);
           if(init==x&&ok!=0) fprintf(g,"%d ",y);
else  {ok=1;fprintf(g,"%d ",x);}

        }while((x!=i||y!=c->inf)&&(x!=c->inf||y!=i));
        if(dd==1) fprintf(g,"%d ",y);
        fprintf(g,"\n");
nrc++;


    }

 }
    else if(c->inf!=t[i]) low[i]=min(low[i],niv[c->inf]);

}

}*/
int main()
{int sum=0,k=0;
    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++){
        fscanf(f,"%d%d",&x,&y);
        adaug(l[x],y);
        adaug(l[y],x);


    }
    int j;
    for(i=1;i<=n;i++){
        if(!use[i]){
         niv[i]=1;
            df(i);
            fprintf(g,"%d\n",nrc);
        for(j=1;j<=n;j++) t[j]=low[j]=niv[j]=use[j]=0;
        okk=1;
 niv[i]=1;
        df(i);

        }



    }
  /*  for(i=1;i<=k;i++) fprintf(g,"%d ",sol2[i]);
for(i=1;i<=n;i++) sum+=sol[i];
fprintf(g,"\n%d\n",sum);
for(i=1;i<=n;i++) if(sol[i]) fprintf(g,"%d ",i);
*/
    return 0;
}