#include #include #include using namespace std; enum Stav { PLUS = 0, MINUS = 1, UZAVREN }; #define INF 1<<20 #define MAXN 5000 #define MAXM 100000 int vrcholy[2*MAXN+1]; int pocet_s[2*MAXN+1]; int sousedi[MAXM]; bool prosly[2*MAXN+1]; int predek[2*MAXN+1]; void nacist_graf() { int n; scanf("%d", &n); int k = 0; for (int i = 1; i <= n; i++) { int ps; scanf("%d", &ps); pocet_s[MAXN+i] = pocet_s[MAXN-i] = ps; vrcholy[MAXN+i] = vrcholy[MAXN-i] = k; for (int j = 0; j < ps; j++) { int v; scanf("%d", &v); sousedi[k++] = v; } prosly[MAXN+i] = prosly[MAXN-i] = false; predek[MAXN+i] = predek[MAXN-i] = 0; } } int sgn(int x) { return x >= 0 ? 1 : -1; } int prochazeni(int s, int c) { list l; /* Pridame do seznamu startovni vrchol */ l.push_front(s); l.push_front(-s); prosly[MAXN+s] = prosly[MAXN-s] = true; while (!l.empty()) { int v = l.front(); l.pop_front(); /* Pokud jsme z fronty vytahli cilovy vrchol, * tak koncime. */ if (abs(v) == c) { return v; } /* Projdeme vsechny sousedy vrcholu v. */ for (int i = 0; i < pocet_s[MAXN+v]; i++) { int soused = sousedi[vrcholy[MAXN+v]+i]; /* Pokud jsme jej uz zpracovali tak pokracujeme * na dalsi. */ if (prosly[MAXN+soused]) { continue; } else { /* Pokud jsme do souseda prisli po hrane se * stejnou znackou, zaradime jej na hlavu * seznamu. */ if (sgn(soused) == sgn(v)) { l.push_front(soused); /* Jinak jej zaradime na konec seznamu. */ } else { l.push_back(soused); } /* Vrchol jsme uz zpracovali. */ prosly[MAXN+soused] = true; /* Nastavime mu vrchol v jako predka. */ predek[MAXN+soused] = v; } } } printf("Cesta nenalezena."); return s; } void rekonstrukce(int v, int s) { /* Dokud nejsme v pocatku, pokracujeme rekurzivne. */ if (abs(v) != s) { rekonstrukce(predek[MAXN+v], s); } else { printf("Prosle vrcholy: "); } /* Nakonec vrcholy vypiseme ve spravnem poradi. */ printf("%d ", abs(v)); } int main() { nacist_graf(); int s, c; scanf("%d %d", &s, &c); int v = prochazeni(s,c); rekonstrukce(v,s); printf("\n"); }