Cod sursa(job #632782)

Utilizator yamahaFMI Maria Stoica yamaha Data 12 noiembrie 2011 12:24:18
Problema Componente biconexe Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 1.89 kb
#include<iostream>
#include<fstream>
#include<stdio.h>

using namespace std;
#define MAX_N 100001
#define MAX_M 200001

struct lista
{
    int nod;
    lista *urm;
}*G[MAX_N];

int N, M, T[MAX_N], L[MAX_N], nv[MAX_N], st[MAX_M][2], lung, nr, v[MAX_N];
char U[MAX_N];

ofstream g("biconex.out",ios::out); 

void push(int i, int j)
{
     st[lung][0]=i;
     st[lung++][1]=j;
}

void pop(int *i, int *j)
{
     *i = st[--lung][0];
     *j = st[lung][1];
}

void DF(int nod)
{
     lista *p;
     int x,y,i,j;
     U[nod]=1;
     L[nod]=nv[nod];
     for(p=G[nod];p!=NULL;p=p->urm)
     {
         if(p->nod!=T[nod] && nv[nod]>nv[p->nod]) push(p->nod,nod);
         if(!U[p->nod])
         {
              nv[p->nod] = nv[nod]+1;
              T[p->nod] = nod;
              DF(p->nod);
              if(L[nod]>L[p->nod]) L[nod]=L[p->nod];
              if(L[p->nod]>=nv[nod])
              {
                   pop(&x,&y);
                   v[1]=x; v[2]=y; i=3;
                   while( (x!=nod || y!=p->nod) && (x!=p->nod || y!=nod) )
                   {pop(&x,&y); v[i]=y; i++;
                   }
                   for(j=1;j<=i-2;j++) g<<v[j]<<" ";
                   if(v[1]!=v[i-1])g<<v[i-1];
                   g<<endl; nr++;
              }
         }
         else if(p->nod!=T[nod] && L[nod]>nv[p->nod])
              L[nod]=nv[p->nod];
     }
}

int main (void)
{
    ifstream f("biconex.in"); 
    g<<endl;
    
    lista *p;
    int x,y,i;
    f>>N>>M;
    for(i=1;i<=M;i++)
    {
         f>>x>>y;
         p=new lista;
         p->urm = G[x];
         p->nod = y;
         G[x]=p;
         p=new lista;
         p->urm = G[y];
         p->nod = x;
         G[y]=p;
    }
    f.close();
    
    for(i=N;i>=1;i--) 
       if(!U[i]) {nv[i]=1; DF(i);}
    g.seekp(0,ios::beg);
    g<<nr;
    
    g.close();  
    return 0;   
}