Show 150 posts per page

1) fai un ciclo for sul vettore dei vertici chiamando una procedura VISITA(v), dopo averli segnati come NUOVI.
VISTA(v) cerca i cicli. Se trovi un ciclo interrompi subito la procedura, perché una foresta non contiene cicli.

Si ha un ciclo se (ad esempio) la lista di adiacenza del nodo v contiene un nodo già visitato che NON è padre del nodo V

Cioè, se il vertice A ha nella sua lista B e B ha nella sua lista C, se C ha nella sua lista A (B ci sarà per forza) hai un ciclo. Ritorni 0, fine.

2) Credo sia più facile, perché il grafo è ORIENTATO, ma il principio è lo stesso. Se il grafo è orientato non dovresti (se non erro) avere nemmeno il problema di verificare il padre, perché se nella lista di adiacenza hai il padre significherebbe che hai un cappio. Correggetemi se sbaglio!! Quindi in questo caso ti basta sapere se il nodo è già stato visitato, in quel caso vuol dire già che hai un ciclo (un cappio è considerabile un ciclo... o no?), ritorni 1

3)Potrebbe essere così?

code:

leggi n
leggi k
leggi B
Calcola(1, n)

procedura Potenza(x,y)
begin

  if (y=2)
     return x*x
  else
    u = parte_intera_inf(y/2)
    a = Potenza(x, u)
    b = Potenza(x, u+1)
    c = a * b
      if y pari
         return c
      else
         return c*x

end

procedura Calcola(i,j)
  begin
    if i=j
       return Potenza(k, i)
    else
     begin
      u = parte_intera_inf((i+j)/2)
      a = Calcola(i, u)
      b = Calcola(u+1, j)
      return a + b;
    end
end

Powered by: vBulletin Version 2.3.1
Copyright © Jelsoft Enterprises Limited 2000 - 2002.