/* P-I-3 Okruzni jizda * Jakub Ruzicka * ctete okruh.txt */#include <iostream>#include <fstream>#include <vector>using namespace std;int main ( int argc, char *argv[] ){// vstupni a vystupni soubory...ifstream vstup("okruh.in");ofstream vystup("okruh.out");// zakladni promennelong int n,m;if( !(vstup >> n) || !(vstup >> m) ) { cerr << "Chyba na vstupu(nepodarilo se nacist zakladni promenne)\n"; vystup.close(); vstup.close(); exit(EXIT_FAILURE);}// pole zakazanych odboceni a ulic- indexovano od 1long int zakazy[n+1][2],ulice[m+1][2],i;// nacteme jednosmerne ulicefor(i=1;i<=m;i++) { vstup >> ulice[i][0]; // odkud vstup >> ulice[i][1]; // kam}// nacteme zakazana odbocenifor(i=1;i<=n;i++) { vstup >> zakazy[i][0]; // odkud vstup >> zakazy[i][1]; // kam }// napred zjistime, jestli je v jednotlivych krizovatkach stejne prichozich a// odchozich ulic, jinak nema smysl ztracet cas s hledanim okruhu...{ long int kontrola[n][2]; for(i=1;i<=n;i++) { kontrola[i][0]=0; kontrola[i][1]=0; } // nulovani for(i=1;i<=m;i++) { kontrola[ulice[i][0]][0]++; // pocet odchozich ulic kontrola[ulice[i][1]][1]++; // pocet prichozich ulic } for(i=1;i<=n;i++) if(kontrola[i][0]!=kontrola[i][1]) { vystup << "Okruzni jizda neexistuje.\n"; vystup.close(); vstup.close(); exit(EXIT_SUCCESS); }}vector<long int> cesta; // pole, ktere bude obsahovat posloupnost ulic okruhu po Stinove Prazechar pouzite[m+1]; // pomocne pole ulic, ktere zajistuje prave jeden vyskyt ulicefor(i=1;i<=m;i++) pouzite[i]=0; // nulovanilong int akt=0,ul,kriz,SpatnaUlice=-1,AktUlice;// a to nejzajimavejsi (ne, ze by to bylo zase TAK zajimave) - hledani okruzni// jizdy. Hruba sila, budeme zkouset tak dlouho, dokud nenajdeme, nebo dojdou// moznosti.while((long int)cesta.size()<=m-1) { if(cesta.empty()) { // jsme na zacatku okruhu, vybirame prvni ulici if(SpatnaUlice>=m) { // vyzkouseli jsme vsechny moznosti, koncime. vystup << "Okruzni jizda neexistuje.\n"; vystup.close(); exit(EXIT_SUCCESS); } else { // zkusime zacit jinou ulici cesta.push_back(SpatnaUlice+1); } } // priradime hodnoty z poli do promennych, usetrime cas hlavne pri delsich // hledanich dalsi ulice okruhu akt=cesta.size()-1; // aktualni usek cesty (kolik ulic uz mame) AktUlice=cesta[akt]; // aktualni ulice kriz=ulice[AktUlice][1]; // aktualni krizovatka // hledame vhodnou ulici, ktera vede z aktualni krizovatky, neni zahrnuta v // okruzni jizde a nekoliduje se zakazem odboceni for(ul=SpatnaUlice+1;( !( (ulice[ul][0]==kriz) && !pouzite[ul] && ( (ulice[AktUlice][0]!=zakazy[ulice[AktUlice][1]][0]) || (ulice[ul][1]!=zakazy[ulice[AktUlice][1]][1]) )) && (ul<=m) );ul++) ; if(ul<=m) { // nasli jsme pokracovani okruzni jizdy cesta.push_back(ul); pouzite[ul]=1; // oznacime si ulici, abychom ji nepouzili vicekrat } else { // tudy to nepujde, vratme se SpatnaUlice=cesta[akt]; // zaznamename si, ze tudy cesta nevede cesta.pop_back(); pouzite[cesta[akt]]=0; // ulici tedy muzeme pouzit }}// vypis okruzni jizdyvector<long int>::iterator ii; for(ii = cesta.begin(); ii != cesta.end(); ii++) vystup << ulice[*ii][0] << " ";vystup << endl;vystup.close(); vstup.close();return EXIT_SUCCESS;}