Cod sursa(job #365996)

Utilizator PopaStefanPopa Stefan PopaStefan Data 20 noiembrie 2009 17:46:26
Problema Componente biconexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 kb
#include<fstream>
#define Nmax 100001

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

int n,vf_stiva;
int dfn[Nmax],low[Nmax];
int numar_componente,nr_ordine;
int viz[Nmax];

struct nod
  {int info;
   nod *urm;
  };
nod *l[Nmax],*a[Nmax];

struct muchie
   {int tata,fiu;
   };
muchie stiva[Nmax];

void citire()
{int i,x,y,m;
fin>>n>>m;
for(i=1;i<=m;i++)
  {fin>>x>>y;
  nod *c;
  c=new nod;
  c->info=y;
  c->urm=l[x];
  l[x]=c;
  c=new nod;
  c->info=x;
  c->urm=l[y];
  l[y]=c;
  }
}

int minim(int x,int y)
{if(x>y) return y;
return x;
}

void salvare(int x,int u)
{muchie p;
nod *c;
int gasit=0;
do{p=stiva[vf_stiva];
   vf_stiva--;
   gasit=0;
   for(c=a[numar_componente];c!=NULL && gasit==0;c=c->urm)
      if(c->info==p.tata) gasit=1;
     if(gasit==0)
      {c=new nod;
       c->info=p.tata;
       c->urm=a[numar_componente];
       a[numar_componente]=c;
      }
  }while(p.tata!=u || p.fiu!=x);
for(c=a[numar_componente];c!=NULL && gasit==0;c=c->urm)
  if(c->info==p.fiu) gasit=1;
if(gasit==0)
   {c=new nod;
   c->info=p.fiu;
   c->urm=a[numar_componente];
   a[numar_componente]=c;
   }
}

void biconex(int u,int tatal)
{int x;
nod *c;
nr_ordine++;
dfn[u]=low[u]=nr_ordine;
for(c=l[u];c!=NULL;c=c->urm)
  {x=c->info;
   if(x!=tatal && dfn[x]<dfn[u])
        {vf_stiva++;
        stiva[vf_stiva].tata=u;
        stiva[vf_stiva].fiu=x;
        }
   if(dfn[x]==0)
     {biconex(x,u);
     low[u]=minim(low[u],low[x]);
     if(low[x]>=dfn[u])
       {numar_componente++;
        salvare(x,u);
       }
     }
    else
      if(x!=tatal)
         low[u]=min(low[u],dfn[x]);
  }
}

int main()
{int i;
nod *c;
citire();
stiva[1].tata=-1;
stiva[1].fiu=3;
biconex(3,-1);
fout<<numar_componente<<'\n';
for(i=1;i<=numar_componente;i++)
  {for(c=a[i];c!=NULL;c=c->urm)
    fout<<c->info<<" ";
   fout<<'\n';
  }
fin.close();
fout.close();
return 0;
}