Cod sursa(job #2610503)

Utilizator horiacoolNedelcu Horia Alexandru horiacool Data 4 mai 2020 22:32:55
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.86 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
 
int p,n,m,ok;
int nivel[100005],l[100005],tata[100005];
int a[100005];
 
struct muchie
{
   int i,j;
}ST[300005];
int u=0;
 
struct nod
{
    int info;
    nod* urm;
}*pt[100005];
 
struct Comp
{
    nod *q;
    Comp* next;
}*Elemx;
 
int K;
 
void InserareNod(nod* &point,int val)
{
    nod* cap = new nod;
    cap->info = val;
    cap->urm = point;
    point = cap;
}
void InserareComp(Comp* &point)
{
    Comp* cap = new Comp;
    cap->q = NULL;
    cap->next = point;
    point = cap;
}
void AfisareNod(nod* &point)
{
    nod* cap = point;
    while( cap != NULL )
    {
        g<<cap->info<<' ';
        cap = cap->urm;
    }
}
void AfisareComp(Comp* &point)
{
    Comp* cap = point;
    while( cap != NULL )
    {
        AfisareNod(cap->q);
 
        g<<'\n';
 
        cap = cap->next;
    }
}
 
void drum(int xp)
{
    while( l[tata[xp]] > l[xp] )
    {
        l[tata[xp]] = l[xp];
 
        xp = tata[xp];
    }
}
 
void CompBiconex(int x,int y)
{
    int ct=0,verif=0;
    K++;
    InserareComp(Elemx);
 
        while( verif == 0 )
        {
            if( a[ST[u].i] != K )
            {
                ct++;
                a[ST[u].i] = K;
 
                InserareNod(Elemx->q,ST[u].i);
 
            }
 
            if( a[ST[u].j] != K )
            {
                ct++;
                a[ST[u].j] = K;
 
                InserareNod(Elemx->q,ST[u].j);
 
            }
 
            if( ST[u].i == x && ST[u].j == y )
               verif = 1;
 
            ST[u].i = ST[u].j = 0;
            u--;
        }
}
 
void DF2(int xp,int r)
{
    nod* cap = pt[xp];
    int y;
 
    while( cap != NULL )
    {
        y = cap->info;
 
        if( y != tata[xp] )
        {
            if( nivel[y] != 0 && nivel[y] < nivel[xp] )
              {
                  if( l[xp] > nivel[y] )
                  {
                     l[xp] = nivel[y];
 
                     drum(xp);
                  }
                  u++;
                  ST[u].i=xp;
                  ST[u].j=y;
              }
              else
              if( nivel[y] == 0 )
              {
                 nivel[y] = nivel[xp] + 1;
 
                 l[y] = nivel[y];
 
                 tata[y] = xp;
 
                 u++;
                 ST[u].i=xp;
                 ST[u].j=y;
 
                 DF2(y,r);
 
                 if( l[y] >= nivel[xp] )
                    CompBiconex(xp,y);
 
               }
          }
          cap = cap->urm;
    }
 
}
 
int main()
{
    int a,b,r;
 
    f>>n>>m;
 
    for(int i=1;i<=n;i++)
        pt[i] = NULL;
 
    Elemx = NULL;
 
    for(int i=1;i<=m;i++)
    {
        f>>a>>b;
        InserareNod(pt[a],b);
        InserareNod(pt[b],a);
    }
 
    r=1;
    tata[r]=0;
    nivel[r]=1;
    l[r]=1;
 
    DF2(r,r);
 
    g<<K<<'\n';
    AfisareComp(Elemx);
 
    return 0;
}