Cod sursa(job #2538602)

Utilizator eusebiu_alexandruMorar Eusebiu eusebiu_alexandru Data 4 februarie 2020 21:09:43
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include<fstream>
#define nmax 100008
#define mmax 200008
using namespace std;
ifstream f ("biconex.in");
ofstream g ("biconex.out");
bool viz[nmax];
int niv[nmax],sus[nmax],start[nmax],t[3][mmax],n,m,i,j,k,varf,element,vecin,coloana,critice;
int num;
struct sa
{
    int f,t;
}stiva[nmax];
void biconex(int u,int tu)
{
    niv[u]=sus[u]=++num;
    coloana=start[u];
    while(coloana)
    {
        vecin=t[0][coloana];
        if(vecin!=tu && niv[vecin]<niv[u])
        {
         stiva[++varf].f=vecin,stiva[varf].t=u;
         if(niv[vecin]==-1)
         {
             biconex(vecin,u);
             sus[u]=min(sus[u],sus[vecin]);
             if(sus[vecin]>=niv[u])
             {
                  critice++;
             }
         }
        }
        else
        {
           if(vecin!=tu)
           {
               sus[u]=min(sus[u],niv[vecin]);
           }
        }
      coloana=t[1][coloana];
    }
}
int main()
{
 f>>n>>m;
 while(m)
 {
   m--;
   f>>i>>j;
   k++;
   t[0][k]=j;
   t[1][k]=start[i];
   start[i]=k;
   k++;
   t[0][k]=i;
   t[1][k]=start[j];
   start[j]=k;
 }
 for(i=1;i<=n;i++)
        niv[i]=-1,sus[i]=-1;
 biconex(1,0);
 g<<critice+1;
}