Cod sursa(job #1611570)

Utilizator ris99Istrate Ruxandra ris99 Data 24 februarie 2016 11:37:39
Problema Componente biconexe Scor 28
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <fstream>

using namespace std;
ifstream f("biconex.in");
ofstream h("biconex.out");
int n,t[10001],l[10001],nv[10001],nr1,nr,k,a[10001][10001],ok,m;
char u[1001],c[1001];
struct nod
{ int inf;
  nod*urm;
};
nod*g[1001];
struct stiva
{ int x,y;

}st[1001];

void adaug(int i,int j)//muchia i,j in stiva
{ st[++k].x=i;
  st[k].y=j;

}

void scoate(int &i,int&j)//extrage muchia i,j in stiva
{ i=st[k].x;
  j=st[k].y;
k--;
}
void adauga_nod(nod*&p,int x)
{ nod*c;
 c=new nod;
 c->inf=x;
 c->urm=p;
 p=c;

}
void citire()
{int x,y,i;
 f>>n>>m;
 for(i=1;i<=m;i++)
 {f>>x>>y;
 adauga_nod(g[x],y);
  adauga_nod(g[y],x);
  }
}
void df(int i)
{ nod*p;
  int x,y;
  u[i]=1;
  l[i]=nv[i];
  for(p=g[i];p!=NULL;p=p->urm)
    {if(p->inf!=t[i]&&nv[i]>nv[p->inf]) adaug(p->inf,i);
    if(!u[p->inf])
    {nv[p->inf]=nv[i]+1;
     t[p->inf]=i;
      df(p->inf);

   if(l[i]>l[p->inf]) l[i]=l[p->inf];
   if(l[p->inf]>=nv[i])
   { nr++;
     do
     {scoate(x,y);
       nr1++;
      a[nr][nr1]=x;
       nr1++;
      a[nr][nr1]=y;


     } while((x!=i||y!=p->inf)&&(x!=p->inf||y!=i));

   }
   }

  else
    if(p->inf!=t[i]&&l[i]>nv[p->inf]) l[i]=nv[p->inf];


}
}
int main()
{ int i,j,j1,aux;
  citire();
  for(i=1;i<=n;i++)
    if(!u[i])
  { nv[i]=1;

    df(i);


  }
  h<<nr<<endl;
  for(i=1;i<=nr;i++)
  { for(j=1;j<=nr1;j++)
    {for(j1=j+1;j1<=nr1;j1++)
    if(a[i][j]>a[i][j1])
    {aux=a[i][j];
    a[i][j]=a[i][j1];
    a[i][j1]=aux;
    }

    }


  }
  for(i=1;i<=nr;i++)
  { ok=1;
    for(j=1;j<=nr1-1;j++)
     if( a[i][j]!=0 && a[i][j]==a[i][j+1]) {h<<a[i][j]<<' ';ok=0;}
     if(ok==1)
        for(j=1;j<=nr1;j++)
        if(a[i][j]!=0) h<<a[i][j]<<' ';
     h<<endl;
  }

    return 0;
}