#include #include #include struct Sloka { Sloka() {} Sloka(int prvni, int druhy, int poradi) : PrvniRym(prvni), DruhyRym(druhy), Poradi(poradi), Skupina(-1), Propojeni(-1), Predchozi(-1) {} int PrvniRym; // číslo prvního rýmu sloky int DruhyRym; // číslo druhého rýmu sloky short int Poradi; // pořadí sloky mezi variantami short int Skupina; // skupina, do které sloka patří short int Propojeni; // skupina, s níž je sloka spojená; -1 pokud s žádnou short int Predchozi; // předchozí sloka (pro rekonstrukci řešení) }; // porovnání podle prvního rýmu bool PodlePrvniho(const Sloka &leva, const Sloka &prava) { return leva.PrvniRym < prava.PrvniRym; } // porovnání podle druhého rýmu bool PodleDruheho(const Sloka &leva, const Sloka &prava) { return leva.DruhyRym < prava.DruhyRym; } int main() { int N; scanf("%d", &N); std::vector> V(N); // seznam všech variant // načtení variant int maxS = 0, min = 0; for (int i=0; i maxS) maxS = S; } // otočíme vstup tak, abychom začínali slokou s nejmenším počtem variant std::rotate(V.begin(), V.begin() + min, V.end()); // předzpracování for (int i=0; i skupiny(maxS, -1); // výsledky pro jednotlivé skupiny std::vector R(maxS, false); // množina R for (int prvni=0; prvni= 0 && skupiny[V[i+1][k].Propojeni] >= 0) { V[i+1][k].Predchozi = skupiny[V[i+1][k].Propojeni]; R[k] = true; } } } // nyní máme R spočítanou a zjistíme, zda lze navázat na první sloku for (int i=0; i vysledek(N); short int aktualni = i; for (int k = N-1; k >= 0; --k) { // kvůli třídění slok se původní pořadí mohlo změnit vysledek[k] = V[k][aktualni].Poradi; aktualni = V[k][aktualni].Predchozi; } // výslednou posloupnost musíme otočit zpátky tak, // aby začínala opět původní první slokou std::rotate(vysledek.begin(), vysledek.begin() + ((vysledek.size() - min) % vysledek.size()), vysledek.end()); for (int k = 0; k < N; k++) printf("%d\n", vysledek[k] + 1); return 0; // stačilo najít libovolné řešení, takže můžeme skončit } } } printf("NEEXISTUJE\n"); // pokud se program dostal až sem, tak nenalezl řešení return 0; }