#include #define MAXN 1000 #define MAXM 1000 struct hrana { struct hrana* dalsi; // další prvek int cil; // cilový vrchol }; struct vrchol { int oznacen; struct hrana* hrany; // spojový seznam na hrany }; // počet vrcholů, hran, označených vrcholů int N, M, posledni; struct vrchol v[MAXN]; // pole vrcholů struct hrana e[MAXM]; // pole hran void projdi(int num); int main(void) { // načteme vstup scanf("%d %d", &N, &M); // inicializace vrcholů for (int i = 0; i < N; i++) { v[i].oznacen = 0; v[i].hrany = NULL; } for (int i = 0; i < M; i++) { // čteme hrany int start, cil; // uložíme v opačném směru scanf("%d %d", &start, &cil); e[i].cil = start; // pridame hranu k vrcholu e[i].dalsi = v[cil].hrany; v[cil].hrany = &e[i]; } for (int i = 0; i < N; i++) { // procházíme vrcholy if (v[i].oznacen == 0) { posledni = i; projdi(i); } } // otestujeme, zda "posledni" je kancelář for (int i = 0; i < N; i++) v[i].oznacen = 0; projdi(posledni); int je_kancelar = 1; for (int i = 0; i < N; i++) if (v[i].oznacen == 0) je_kancelar = 0; if (je_kancelar) // vypíšeme výsledek printf("Přijímací kancelář je %d.\n", posledni); else printf("V pekle není přijímací kancelář!\n"); } void projdi(int num) { v[num].oznacen = 1; // označíme vrchol struct hrana* hr = v[num].hrany; // projdeme všechny hrany z vrcholu while (hr != NULL) { if (v[hr->cil].oznacen == 0) projdi(hr->cil); hr = hr->dalsi; } }