Cod sursa(job #365990)

Utilizator PopaStefanPopa Stefan PopaStefan Data 20 noiembrie 2009 17:37:26
Problema Componente biconexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 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;
int i;
nod *c;
viz[x]=numar_componente;
viz[u]=numar_componente;
do{p=stiva[vf_stiva];
   vf_stiva--;
   viz[p.tata]=numar_componente;
   viz[p.fiu]=numar_componente;
  }while(p.tata!=u || p.fiu!=x);
for(i=1;i<=n;i++)
  if(viz[i]==numar_componente)
    {c=new nod;
   c->info=i;
   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;
}