struct list *next;
}
typedef struct list list;

==

In contiuare vom prezenta o metoda care este de $3-4$ ori mai rapida (adica parcurgerile DF , BF sau altii algoritmi ruleaza de $3-4$ ori mai rapid cand graful este stocat astfel), dar are ca dezavantaj necesitatea de a citi de doua ori fisierul de intrare.

#include <stdlib.h>
#include <stdio.h>

int N, M, *G[N], Deg[N];@}

int N, M, *G[N], Deg[N];

int main(void)@}

int main(void)

{
    int i, j;

Sporul de viteza se datoreaza faptului ca se folosesc vectori in loc de pointeri si struct-uri. Daca ne permite memoria putem evita citirea de doua ori a fisierul prin pastrarea muchiilor intr-o lista de muchii si apoi, dupa calcularea gradelor, inserarea muchiilor in liste. Pentru a demonstra eficienta acestei metode faceti urmatorul test: implementati o sursa cu pointeri si struct si implementati un BF, apoi scrieti codul de mai sus cu urmatoarele modificari:

p(pre). {@...@}
{@for (i = 0; i < N; i++)@}
{@{@}
{@      G[i] = (int *) malloc((Deg[i]+1)*sizeof(int));@}
{@      G[i][Deg[i]] = -1;@}
{@      Deg[i] = 0;@}
{@}@}
{@...@}

== code(c) |
...
for (i = 0; i < N; i++)
{
      G[i] = (int *) malloc((Deg[i]+1)*sizeof(int));
      G[i][Deg[i]] = -1;
      Deg[i] = 0;
}
...
==

si implementati BF astfel:

p(pre). {@void BF@}
{@{@}
{@      int Q[N], ql, qr, *p;@}
{@      char U[N];@}
{@      memset(U, 0, sizeof(U));@}
{@      U[Q[ql = qr = 0] = n] = 1;@}
{@      for (; ql <= qr; ql++)@}
{@              for (p = G[Q[ql]]; *p != -1; p++)@}
{@                      if (!U[*p]) U[Q[++qr] = *p] = 1;@}
{@}@}

== code(c) |
void BF
{
      int Q[N], ql, qr, *p;
      char U[N];
      memset(U, 0, sizeof(U));
      U[Q[ql = qr = 0] = n] = 1;
      for (; ql <= qr; ql++)
              for (p = G[Q[ql]]; *p != -1; p++)
                      if (!U[*p]) U[Q[++qr] = *p] = 1;
}
==

Apoi, incercati sa vedeti diferenta de timp intre cele doua programe... impresionant, nu?

h3. Suma a doua numere mari

p(pre). {@void add(int A[], int B[])@}
{@{@}
{@      int i, t = 0;@}
{@      for (i=1; i<=A[0] || i<=B[0] || t; i++, t/=10)@}
{@              A[i] = (t += A[i] + B[i]) % 10;@}
{@      A[0] = i - 1;@}
{@}@}

== code(c) |
void add(int A[], int B[])
{
      int i, t = 0;
      for (i=1; i<=A[0] || i<=B[0] || t; i++, t/=10)
              A[i] = (t += A[i] + B[i]) % 10;
      A[0] = i - 1;
}
==

h3. Inmultirea unui numar mare cu un numar mic

p(pre). {@void mul(int A[], int B)@}
{@{@}
{@      int i, t = 0;@}
{@      for (i = 1; i <= A[0] || t; i++, t /= 10)@}
{@              A[i] = (t += A[i] * B) % 10;@}
{@      A[0] = i - 1;@}
{@}@}

== code(c) |
void mul(int A[], int B)
{
      int i, t = 0;
      for (i = 1; i <= A[0] || t; i++, t /= 10)
              A[i] = (t += A[i] * B) % 10;
      A[0] = i - 1;
}
==

h3. Inmultirea unui numar mare cu un numar mare

p(pre). {@void mul(int A[], int B[])@}
{@{@}
{@      int i, j, t, C[];@}
{@      memset(C, 0, sizeof(C));@}
{@      for (i = 1; i <= A[0]; i++)@}
{@      {@}
{@              for (t=0, j=1; j <= B[0] || t; j++, t/=10)@}
{@                      C[i+j-1]=(t+=C[i+j-1]+A[i]*B[j])%10;@}
{@              if (i + j - 2 > C[0]) C[0] = i + j - 2;@}
{@      }@}
{@      memcpy(A, C, sizeof(C));@}
{@}@}

== code(c) |
void mul(int A[], int B[])
{
      int i, j, t, C[];
      memset(C, 0, sizeof(C));
      for (i = 1; i <= A[0]; i++)
      {
              for (t=0, j=1; j <= B[0] || t; j++, t/=10)
                      C[i+j-1]=(t+=C[i+j-1]+A[i]*B[j])%10;
              if (i + j - 2 > C[0]) C[0] = i + j - 2;
      }
      memcpy(A, C, sizeof(C));
}
==

h3. Scaderea a doua numere mari

p(pre). {@void sub(int A[], int B[])@}
{@{@}
{@      int i, t = 0;@}
{@      for (i = 1; i <= A[0]; i++)@}
{@              A[i] += (t = (A[i] -= B[i] + t) < 0) * 10;@}
{@      for (; A[0] > 1 && !A[A[0]]; A[0]--);@}
{@}@}

== code(c) |
void sub(int A[], int B[])
{
      int i, t = 0;
      for (i = 1; i <= A[0]; i++)
              A[i] += (t = (A[i] -= B[i] + t) < 0) * 10;
      for (; A[0] > 1 && !A[A[0]]; A[0]--);
}
==

h3. Impartirea unui numar mare la un numar mic

p(pre). {@void div(int A[], int B)@}
{@{@}
{@      int i, t = 0;@}
{@      for (i = A[0]; i > 0; i--, t %= B)@}
{@              A[i] = (t = t * 10 + A[i]) / B;@}
{@      for (; A[0] > 1 && !A[A[0]]; A[0]--);@}
{@}@}

== code(c) |
void div(int A[], int B)
{
      int i, t = 0;
      for (i = A[0]; i > 0; i--, t %= B)
              A[i] = (t = t * 10 + A[i]) / B;
      for (; A[0] > 1 && !A[A[0]]; A[0]--);
}
==

h3. Restul unui numar mare la un numar mic

p(pre). {@int mod(int A[], int B)@}
{@{@}
{@      int i, t = 0;@}
{@      for (i = A[0]; i > 0; i--)@}
{@              t = (t * 10 + A[i]) % B;@}
{@      return t;@}
{@}@}

== code(c) |
int mod(int A[], int B)
{
      int i, t = 0;
      for (i = A[0]; i > 0; i--)
              t = (t * 10 + A[i]) % B;
      return t;
}

h2. AVL-uri (ideea originala de la Radu Berinde - again)