Babbo Natale

Babbo Natale è un essere risaputamente pigro e per questo Natale, stanco di dovere ogni anno progettare miriadi di giocattoli diversi, ha deciso di fare produrre alle sue fabbriche di giocattoli solo tre tipi di giocattoli.

Babbo Natale vuole però comunque rendere felici tutti i bambini del mondo e sa che un bambino è felice se e solo se ha ricevuto un regalo diverso da quello ricevuto da ognuno dei suoi amici.

Per rendere felice un bambino, quindi, Babbo Natale deve portargli un regalo diverso da quelli dei suoi amici; quindi, se a un bambino viene dato un regalo di tipo 1, ai suoi amici deve essere dato necessariamente un regalo di tipo 2 o di tipo 3.
Babbo Natale sa che in questo modo potrebbe non essere possibile accontentare tutti i bambini, ma è troppo pigro per trovare una soluzione migliore.

Per realizzare il suo progetto Babbo Natale si è procurato la lista completa delle amicizie dei bambini di tutto il mondo, e ha dato a un elfo il compito di approntare una seconda lista contenente, per ogni bambino, il tipo del regalo che deve essergli consegnato.
La notte di Natale, però, al ritorno dal viaggio attorno al mondo durante il quale visita le case di tutti i bambini, Babbo Natale si accorge che la lista fornitagli dall’elfo contiene degli errori: lo stesso tipo di regalo è stato assegnato ad almeno due bambini che risultano essere amici.

A Babbo Natale sono rimaste poche ore per rimediare al danno fatto dall’elfo.
Il tuo compito è aiutare Babbo Natale fornendogli una lista con i nomi di tutti i bambini a cui deve essere sostituito il regalo e il nuovo tipo di regalo che deve essere assegnato a ognuno di loro.
Dato che il tempo stringe, la lista deve essere la più corta possibile.
Nel caso che non sia possibile accontentare tutti i bambini, la lista deve contenere l’unico intero -1.

Dati in input

Il file di input, di nome input.txt, contiene sulla prima riga due interi: il numero N dei bambini che Babbo Natale deve visitare e il numero M delle relazioni di amicizia esistenti tra i bambini.
Ciascuna delle M righe successive è composta da una coppia di interi A e B, separati da uno spazio, che indicano che il bambino A è amico di B e viceversa (i bambini sono numerati da 1 a N).
Dopo le suddette M righe c’è un’ultima riga contenente una lista di N interi compresi tra 1 e 3.
Il primo intero rappresenta il tipo del regalo assegnato dall’elfo al primo bambino, il secondo il tipo assegnato al secondo bambino e così via.

Dati in output

Il file di output, di nome output.txt, deve contenere nella prima riga il numero di cambiamenti effettuati all’assegnamento dell’elfo, o -1 se non è possibile accontentare tutti i bambini.
Se è possibile accontentare tutti i bambini, la seconda riga deve contenere una sequenza di N interi compresi tra 1 e 3.
Il primo intero rappresenta il tipo del regalo assegnato dalla vostra soluzione al primo bambino, il secondo il tipo assegnato al secondo bambino e così via.

Assunzioni

• Il tempo limite di esecuzione è fissato in 0,3 secondi.
• Presi comunque due bambini al mondo esiste sempre una catena di amicizie che li lega.
• 1 <= N <= 300
• 1 <= M <= 4000

Esempio

input.txt	output.txt
5 7 1 2 1 3 1 4 2 5 3 5 3 4 5 4 3 2 3 3 3	2 3 2 2 1 3

#include 
#include 
//+++++++++++++++++++++++++++++++++ ADT lista di amici +++++++++++++++++++++++++
struct nodo_amico
{
   int        amico;
   nodo_amico *link;
};

typedef struct nodo_amico *pnodo_amico;

void aggiungi(pnodo_amico *pn, int x)
{
   pnodo_amico p=(pnodo_amico)malloc(sizeof(struct nodo_amico));
               p->amico=x;
               p->link=(*pn);
   (*pn)=p;
}
//+++++++++++++++++++++++++++++++++ BAMBINO ++++++++++++++++++++++++++++++++++++
struct bambino
{
   int         controllare;        // da controllare?
   int         regali[4];          // 0: assegnato --- 1, 2, 3: assegnabili?
   pnodo_amico lista;              // inizio lista degli amici
};
//+++++++++++++++++++++++++++++++++ ADT lista di bambini +++++++++++++++++++++++
struct nodo_bambino
{
   int          bambino;
   nodo_bambino *link;
};

typedef struct nodo_bambino *pnodo_bambino;

void aggiungi(pnodo_bambino *pn, int x)
{
   pnodo_bambino p=(pnodo_bambino)malloc(sizeof(struct nodo_bambino));
                 p->bambino=x;
                 p->link=(*pn);
   (*pn)=p;
}

int controlla(pnodo_bambino *pn)
{
   int           bambino = (*pn)->bambino;  
   pnodo_bambino p       = (*pn);
                 (*pn)   = (*pn)->link;   
   free(p);   
   
   return bambino;
}
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
int main()
{
  int N;                            // numero di bambini
  int M;                            // numero di amicizie
  bambino *i_bambini;               // la situazione dei bambini
  
  FILE *file;
  file=fopen("input.txt", "r"); 
  fscanf(file, "%d %d", &N, &M);
  i_bambini=(bambino *)calloc(N+1, sizeof(bambino));
  for(int i=1; i <= N; i++)
  {
     i_bambini[i].controllare=1;      // da controllare
     i_bambini[i].regali[1]  =1;      // regali tutti disponibili
     i_bambini[i].regali[2]  =1;
     i_bambini[i].regali[3]  =1;
     i_bambini[i].lista      =NULL;   // nessun amico...
  }  
  int bambino1,                       // carica le amicizie dei bambini
      bambino2;
  for(int i=1; i <= M; i++)
  {
     fscanf(file, "%d %d", &bambino1, &bambino2);     
     aggiungi(&(i_bambini[bambino1].lista), bambino2);
     aggiungi(&(i_bambini[bambino2].lista), bambino1);
  }
  for(int i=1; i <= N; i++)
     fscanf(file, "%d", &(i_bambini[i].regali[0])); // scelta iniziale regalo
  fclose(file); 
  //++++++++++++++++++++++++++++++++++++ controlla tutti i bambini +++++++++++++ 
  int risposta=0;
  pnodo_bambino lista_bambini=NULL;        
  aggiungi(&lista_bambini, 1);           // primo bambino da controllare
  
  int         b, bb,
              r, rr;  
  pnodo_amico pa;
  do
  {
      b=controlla(&lista_bambini);       // bambino da controllare
      i_bambini[b].controllare=0;        // non più...
      r=i_bambini[b].regali[0];          // il suo regalo attuale
      if(i_bambini[b].regali[r] == 0)    // se deve cambiare regalo...
      {      
          rr=r;                    
          for(int i=1; i <= 3; i++)      // trovane uno disponibile
          {
              if(i_bambini[b].regali[i] == 1)
              {
                  rr=i;
                  break;
              }
          }
          
          if(rr != r)                    // se c'è un regalo diverso per b
          {
             r=rr;                      
             i_bambini[b].regali[0]=rr;
             risposta++;                
          }
          else
          {
             file = fopen("output.txt", "w");
             fprintf(file, "-1");
             fclose(file);
             return 0;
          }
      }
      pa=i_bambini[b].lista;                // elimina la disponibilità di r
      while(pa != NULL)                     // agli amici di b
      {
          bb=pa->amico;         
          i_bambini[bb].regali[r]=0;        // r non è disponibile per bb
          if(i_bambini[bb].controllare)     // se non ancora controllato
             aggiungi(&lista_bambini, bb);  // ricordati di controllare bb
          pa=pa->link;
      }
  } while(lista_bambini != NULL);
  //+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
  file = fopen("output.txt", "w");
  fprintf(file, "%d\n", risposta);
  for(int i=1; i <= N; i++)
      fprintf(file, "%d ", i_bambini[i].regali[0]);
  fclose(file);
  return 0;
}