Selezioni nazionali IOI 2002

Condominio (COND, D=4)

Il problema

Le tubature di un condominio sono state rimaneggiate così tante volte che nessuno si ricorda più bene come l'acqua dovrebbe essere distribuita. Gli operai hanno creato molti raccordi temporanei, che non sono stati più rimossi, creando una vera ragnatela di tubi e giunture.

Quando però una serie di tubi sono collegati fino a formare un anello in cui l'acqua scorre circolarmente la situazione è particolarmente grave, perché l'acqua può cominciare ad andare in circolo, creando sbalzi di pressione e scoppi delle tubature.

Il vostro compito è aiutare l'amministratore del condominio a risolvere questo problema. Per fare ciò, dovete aiutarlo a trovare tutti gli anelli, cioè tutte le sequenze di tubi che partono e terminano nello stesso giunto (senza passare mai due volte per lo stesso giunto), e in cui l'acqua scorre sempre nello stesso verso. Per esempio, nella rete di tubi e giunti rappresentata in figura 1, dove le frecce rappresentano lo scorrimento dell'acqua, ci sono due anelli: 3-6-7-4 e 3-6-7-8-4. Notate che gli stessi anelli possono anche essere descritti, per esempio, come 7-4-3-6 e 4-3-6-7-8 (cioè il vertice di partenza non conta).

Figura 1: Un esempio di rete condominiale.

Dati in input

Il file di input, di nome input.txt, contiene sulla prima riga due interi G e T, che sono il numero di giunti e di tubi. Ogni tubo collega un giunto a un altro giunto. Su ciascuna delle successive T righe compaiono due interi, che sono il giunto di partenza e quello di arrivo di un tubo. Più precisamente, nella riga i del file compaiono il giunto iniziale e quello finale del tubo (i-1)-esimo (sia i giunti che i tubi sono numerati a partire da uno). L'acqua scorre dal giunto di partenza a quello di arrivo.

Dati in output

Il file di output, di nome output.txt, contiene una lista di anelli presenti nella rete condominiale. Ogni anello viene descritto tramite la sequenza dei giunti che attraversa, separati da uno spazio.

Assunzioni

• il tempo limite di esecuzione è fissato in 5 secondi;
• 1 <= G <= 200;
• non ci sono mai più di 100000 anelli nella rete condominiale;
• il file di input non contiene altri caratteri oltre a quelli indicati nel testo;
• il file di output non deve contenere altri caratteri oltre a quelli indicati nel testo; inoltre, il programma non deve produrre alcun altro input/output oltre a quelli indicati: deve limitarsi a leggere il file di input e a scrivere i risultati sul file di output;
• i file di input/output vanno specificati senza alcuna indicazione di path, e quindi verranno aperti in C con un'istruzione tipo

  			fr = fopen( "input.txt", "r" );
  			fw = fopen( "output.txt", "w" );
  		

  e in Pascal con un'istruzione tipo

  			assign( fr, 'input.txt' ); reset( fr );
  			assign( fw, 'output.txt' ); rewrite( fw );
  		

Punteggio

1. se il vostro programma emette una sequenza di giunti che non è un anello, emette due volte lo stesso anello, oppure se supera i limiti di tempo di esecuzione imposti, riceverà zero punti;
2. altrimenti, il vostro programma riceverà p·A punti, dove p è il rapporto tra il numero di anelli che siete riusciti a trovare e quelli esistenti.

Esempio di input/output

File input.txt

8 9
1 2
2 3
4 3
5 6
3 6 
6 7
7 4
7 8
8 4
	 

File output.txt

3 6 7 8 4
4 3 6 7