#!/usr/bin/env python3 # 27-Z4-6: Příprava grilovačky # Formát: # počet vrcholov # vrchol0 sused1 sused2 ... # vrchol1 sused1 sused2 ... # ... # Príklad vstupu: # 3 # 0 1 2 # 1 # 2 1 # Výstup: # 1 # 2 # 0 def DFS(vrchol): otvorene[vrchol] = True # Aktuálny vrchol si označíme, že z neho začíname prehľadávať for sused in graf[vrchol]: # Prejdeme všetkých susedov aktuálneho vrcholu if otvorene[sused]: # Ak sme už suseda raz navštívili, ale ešte sme ho úplne nespracovali return False # ... tak sme našli cyklus a prehľadávanie ukončíme s False if spracovane[sused]: # Ak natrafíme na už spracovaný vrchol continue # ... tak ho ignorujeme (všetky závislosti z neho sú už vyriešené) if not DFS(sused): # A ináč spustíme rekurzívne prehľadávanie zo suseda return False # ... v prípade, že detegujeme cyklus ihneď ukončíme s False # V tomto momente sme už všetkých susedov spracovali a vyriešili vystup.append(vrchol) # Pridáme aktuálny vrchol na výstup otvorene[vrchol] = False # ... vrchol opúšťame (už nie je otvorený) spracovane[vrchol] = True # ... a zároveň už je spracovaný return True # Vrátime True ak nebol detekovaný cyklus def prehladaj(): global vystup global otvorene global spracovane vystup = [] otvorene = [False]*(N) spracovane = [False]*(N) # Prejdeme všetky vrcholy a z každého nespracovaného spustíme prehľadávanie for i in range(0, N): if not spracovane[i]: if not DFS(i): return False return True def main(): global graf global N N = int(input()) # Načítame počet vrcholov graf = [[]]*(N) # Inicializujeme graf (ako prázdny zoznam zoznamov susedov) for i in range(0, N): riadok = list(map(int, input().split())) # Načítame riadok (čísla vrcholov oddelené medzerou) vrchol = riadok.pop(0) # Prvé číslo udáva vrchol ... graf[vrchol] = riadok # ... a zvyšné zoznam jeho susedov if not prehladaj(): # Spustíme samotné prehľadávanie print("Činnosti nie je možné zoradiť") return for vrchol in vystup: # A vypíšeme jednotlivé činnosti v správnom poradí print(vrchol) if __name__ == "__main__": main()