Cod sursa(job #394986)

Utilizator lorandCsorba Lorand-Alexandru lorand Data 11 februarie 2010 21:35:32
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.44 kb
using namespace std;
#include<fstream>
ofstream fout("biconex.in");
struct nod
{
       int vf;
       nod* next;
};
struct muchie
{
       int i;
       int j;
};
int n,m,y,vs,*v,*viz,*componenta[100005],*h;
nod   *G[100005];
muchie *stiva;
void addarc(int,int);
int dfs(int,int,int);
void comp(int,int);
int main()
{
    int i,x,d;
    ifstream fin("biconex.out");
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
                     fin>>x>>y;
                     addarc(x,y);
                     addarc(y,x);
    }
    v=new int[n+1];
    h=new int[n+1];
    for(i=0;i<=n;++i)
       v[i]=h[i]=0;
    stiva=new muchie[m+1];
    viz=new int[n+1];
    y=0;
    x=dfs(1,0,1);
    fout<<y<<'\n';
    for(i=1;i<=y;++i)
    {
                     d=componenta[i][0];
                     for(x=1;x<=d;++x)
                        fout<<componenta[i][x]<<' ';
                     fout<<'\n';
    }
    return 0;
}
void addarc(int i,int j)
{
     nod *p=new nod;
     p->vf=j;
     p->next=G[i];
     G[i]=p;
}
int dfs(int k,int t,int niv)
{
      int niv_min,aux;
      nod *p;
      if(v[k])
        return h[k];
      else
      {
          v[k]=1;
          h[k]=niv_min=niv;
          for(p=G[k];p;p=p->next)
             if(p->vf!=t)
               if(v[p->vf]==0 || h[p->vf]<niv)
               {
                          stiva[++vs].i=p->vf;
                          stiva[vs].j=k;
                          if(v[p->vf])
                            aux=dfs(p->vf,k,niv+1);
                          else
                          {
                              aux=dfs(p->vf,k,niv+1);
                              if(niv<=aux)
                                comp(p->vf,k);
                          }
                          if(aux<niv_min)
                            niv_min=aux;
               }
      }
      return niv_min;
}
void comp(int i,int j)
{
     int x;
     muchie m;
     componenta[++y]=new int[n+1];
     for(x=1;x<=n;++x)
        viz[x]=0;
     x=0;
     do{
              m=stiva[vs--];
              if(viz[m.i]==0)
              {
                             componenta[y][++x]=m.i;
                             viz[m.i]=1;
              }
              if(viz[m.j]==0)
              {
                             componenta[y][++x]=m.j;
                             viz[m.j]=1;
              }
     }while(m.i != i || m.j != j);
     componenta[y][0]=x;
}