Сорткунии топологӣ

Шарт

Графи равонашудаи бе давра бо $n$ қулла ва $m$ канор дода шудааст. Лозим аст чунин тартиби қуллаҳоро ёфт, ки ҳар як канор аз қуллаи бо индекси хурдтар ба қуллаи бо индекси калонтар барад.

Ба ибораи дигар, бояд ҷойивазкунии қуллаҳо (тартиби топологӣ)-ро ёфт, ки ба ҳамаи канорҳои граф мувофиқат кунад: агар канори равонашудаи $x \rightarrow y$ вуҷуд дошта бошад, пас қуллаи $x$ бояд пеш аз қуллаи $y$ дар ҷойивазкунии ҷустуҷӯшаванда ояд.

Ҳал

Барои ҳал кардани ин масъала ҷустуҷӯ дар амиқӣ (DFS)-ро истифода мебарем.

Ҳангоми оғоз аз қуллаи муайяни $x$ DFS кӯшиш мекунад аз рӯйи ҳамаи канорҳои аз он баромада гузарад. Он дар он канорҳое меистад, ки нӯгҳояшон аллакай пештар боздид шуда буданд, ва ба таври рекурсивӣ гардишро аз рӯйи боқимондаҳо идома медиҳад. Ҳамин тавр, то лаҳзаи анҷоми ҳамаи қуллаҳое, ки аз дастрасанд, аллакай коркард мешаванд.