Cod sursa(job #632771)

Utilizator yamahaFMI Maria Stoica yamaha Data 12 noiembrie 2011 12:06:44
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 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;
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;
     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);
                   g<<x<<" "<<y;
                   while( (x!=nod || y!=p->nod) && (x!=p->nod || y!=nod) )
                   {pop(&x,&y); g<<" "<<y;}
                   
                   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=1;i<=N;i++) 
       if(!U[i]) {nv[i]=1; DF(i);}
    g.seekp(0,ios::beg);
    g<<nr;
    
    g.close();  
    return 0;   
}