/**************************************************************************

1 - nacti dvojici jmen X, Y
2 - projdi vsechny existujici mnoziny a zjisti ve kterych je X a Y ulozeno
   * jestlize takova mnozina neexistuje, vytvor ji a uloz do ni X, Y
   * jestlize byla nalezena jen jedna mozina, uloz do ni X i Y
   * byly-li nalezeny dve mnoziny, spoj je v mnozinu jedinou
3 - vrat se na krok 1, jestlize uz nejsi na konci souboru 

**************************************************************************/

#include <stdio.h>

/*
implementace mnoziny
	prvky jsou cela cisla
	umi se sloucit s jinou mnozinou
*/
class mnozina {
	class prvek {
	public:
		int jmeno;					// jmeno by mohlo byt string, ale pro zjednoduseni staci asi i cislo
		prvek *dalsi;
		
		prvek() {
			dalsi = NULL;
		}
	};

public:
	prvek *prvni, *posledni, *aktual;
	int spojena;
	
	mnozina() {
		prvni = posledni = NULL;
		spojena = 0;
	}
	
	void pridejJmeno(int j) {		// mel by kontrolovat, zda uz jedno takove neexistuje
		if (posledni != NULL) {
			posledni = posledni->dalsi = new prvek();
		} else {
			posledni = new prvek();
			prvni = posledni;
		}
		posledni->jmeno = j;
	}
	
	int obsahujeJmeno(int j) {
		prvek *pomoc = prvni;
		while (pomoc != NULL) {
			if (pomoc->jmeno == j) return 1;
			pomoc = pomoc->dalsi;
		}
		return 0;
	}
	
	~mnozina() {
		if (!spojena) {
			prvek *pomoc;
			while (prvni != posledni) {
				pomoc = prvni;
				prvni = pomoc->dalsi;
				delete pomoc;
			}
			delete posledni;
		}
	}
	
	void pripojMnozinu(mnozina *m) {
		posledni->dalsi = m->prvni;
		posledni = m->posledni;
		m->spojena = 1;
	}

	void start() {
		aktual = prvni;
	}

	int *krok() {
		int *i = &(aktual->jmeno);
		if (aktual != NULL)	{
			aktual = aktual->dalsi;
			return i;
		} else return NULL;
	}
};


/*
implementace jednosmerne fronty
	prvky jsou mnoziny
	umi prohledat zda a ktera mnozina obsahuje konkretni hodnotu
*/
class seznamMnozin {
	class prvek {
	public:
		mnozina m;
		prvek *dalsi;

		prvek() {
			dalsi = NULL;
		}
	};

public:
	prvek *prvni, *posledni, *aktual;

	seznamMnozin() {
		prvni = posledni = new prvek;
	}
	
	mnozina *novaMnozina() {
		mnozina *m = &(posledni->m);
		posledni = posledni->dalsi = new prvek;
		return m;
	}

	void odstranMnozinu(mnozina *m) {
		prvek *pomoc = prvni, *ppred = NULL;
		while (pomoc != posledni) {
			if (&(pomoc->m) == m) {
				if (ppred != NULL) {
					ppred->dalsi = pomoc->dalsi;
				} else
					prvni = prvni->dalsi;
				delete pomoc;
				break;
			}
			ppred = pomoc;
			pomoc = pomoc->dalsi;
		}
	}

	mnozina *obsahujeJmeno(int j) {
		prvek *pomoc = prvni;
		while (pomoc != posledni) {
			if (pomoc->m.obsahujeJmeno(j)) return &(pomoc->m);
			pomoc = pomoc->dalsi;
		}
		return NULL;
	}
	
	~seznamMnozin() {
		prvek *pomoc;
		while (prvni != posledni) {
			pomoc = prvni;
			prvni = pomoc->dalsi;
			delete pomoc;
		}
		delete posledni;
	}

	void start() {
		aktual = prvni;
	}

	mnozina *krok() {
		mnozina *m = &(aktual->m);
		if (aktual != posledni) {
			aktual = aktual->dalsi;
			return m;
		} else return NULL;
	}
};


/* dvojice jmen */
int pl[] = {10, 13, 15, 10, 11, 18, 1, 5, 14, 11, -1};
int pp[] = {11, 14, 10, 11, 10, 15, 2, 4, 04, 15, -1};


int main(void) {
	seznamMnozin mnoziny;							// seznam obsahujici mnoziny


	/************************
		vlastni algoritmus
	*************************/
	int i = 0;
	while (pl[i] != -1) {							// pole dvojic jmen je ukonceno -1
		mnozina *a = mnoziny.obsahujeJmeno(pl[i]);	// zda je prvni jmeno nalezeno v nejake mnozine | NULL znaci, ze nikoli
		mnozina *b = mnoziny.obsahujeJmeno(pp[i]);	// zda je druhe jmeno nalezeno v mnozine
		if ((a == NULL)&&(b == NULL)) {				// ani jedno ze jmen se v zadne mnozine nenachazi ...
			mnozina *p = mnoziny.novaMnozina();		// ...vytvor proto novou mnozinu a ...
			p->pridejJmeno(pl[i]);					// ...oba prvky tam uloz ...
			p->pridejJmeno(pp[i]);					// ...ten taky
		}
		if (a != b) {								// obe jmena jsou v jinych mnozinach nebo jedno z nich neni v zadne mnozine
			if ((a != NULL)&&(b != NULL)) {			// jestlize kazde ze jmen lezi v jine mnozine ...
				a->pripojMnozinu(b);				// ...potom obe mnoziny spoj a ...
				mnoziny.odstranMnozinu(b);			// ...pritom tu nepotrebnou odstran
			} else {									// jestlize jedno ze jmen je nove ...
				if (a != NULL) a->pridejJmeno(pp[i]);	// ... a neni to to prvni, pak druhe uloz do mnoziny toho prvniho
				if (b != NULL) b->pridejJmeno(pl[i]);	// ... nebo to neni to druhe, pak to uloz obracene
			}
		}
		i ++;
	}

	/* vypis mnozin */
	mnozina *p;
	int *jmeno;

	mnoziny.start();
	while ((p = mnoziny.krok()) != NULL) {
		p->start();
		while ((jmeno = p->krok()) != NULL) {
			printf("%d ", *jmeno);
		}
		printf("\n");
	}

	return 0;
}