Forum programmazione

[Bit]

Code: Select all

#include <stdio.h>
#define N 100

int main(void)
{
       int i, j, p, q, id[N], sz[N];
       
       for(i=0; i < N; ++i){
          id[i] = i;
          sz[i] = 1;
       }
       while(scanf("%d %d", &p, &q) == 2){
              for(i = p; i != id[i]; i = id[i]);
              for(j = q; j != id[j]; j = id[j]);
              if(i == j)
               continue;
              if(sz[i] < sz[j]){
               id[i] = j;
               sz[j] += sz[i];
             }
             else {
                       id[j] = i;
                       sz[i] += sz[j];
             }
             printf("%d %d\n", p, q);
      }
}


[k8]

uhm..
cos'è?

magari esponi il problema , e descrivi la risoluzione in pseudocofica,
in questa sezione è meglio usar solo pseudocodice

[Bit]

immaginiamo di avere un dato oggetto p e un oggetto q, e dobbiamo stabilire una relazione tra di loro, ovvero in partenza vedere se sono connessi, se non lo sono provvediamo a connetterli. Con questo algoritmo si può fare.. i due for servono a fare un operazione di find e le successive itruzioni servono come union, cioè connette l'oggetto p con quello q.. successivamente se l'oggetto q è connesso con r lo sarà anche p. Questo algoritmo serve a risolvere dei problemi riguardanti le connessioni tra miliardi di pc

[k8]

interessante

[Bit]

Code: Select all

#include <stdio.h>
#define N 100

int main(void)
{
       int i, j, p, q, id[N], t;
       
       for(i=0; i < N; ++i){
          id[i] = i;
       }
       while(scanf("%d %d", &p, &q) == 2){
              if(id[p] == id[q])
               continue;
              for(t = id[p], i=0; i < N; ++i)
                 if(id[i] == t)
                  id[i] = id[q];
             printf("%d %d\n", p, q);
       }
}


guardate questo programma, e immagine di avere 10^6 oggetti (N = 10^6) e 10^9 coppie in un computer ke fa 10^9 istruzioni al secondo, supponendo ke il while richieda non + di 10 istruzioni, quanti giorni necessita questo algoritmo per terminare le operazioni?

[Bit]

credo ke la soluzione sia 10^7 sec...