Cod sursa(job #1845337)

Utilizator horiacoolNedelcu Horia Alexandru horiacool Data 11 ianuarie 2017 12:51:44
Problema Componente biconexe Scor 76
Compilator cpp Status done
Runda Arhiva educationala Marime 3.52 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;
    K++;
    InserareComp(Elemx);

    if( ST[u].i != x && ST[u].j != y )
    {
        while(( ST[u].i != x || ST[u].j != y )&&( ST[u].i != y || ST[u].j != x ))
        {
            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);

            }

            ST[u].i = ST[u].j = 0;
            u--;
        }

        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);

        }

        ST[u].i = ST[u].j = 0;
        u--;
    }
    else
    {
        InserareNod(Elemx->q,ST[u].i);
        InserareNod(Elemx->q,ST[u].j);

        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=n;
    tata[r]=0;
    nivel[r]=1;
    l[r]=1;

    DF2(r,r);

    g<<K<<'\n';
    AfisareComp(Elemx);

    return 0;
}