1.9 KiB
Zadania domowe z sortowania topologicznego i silinie spójnych składowych
Rozwiązanie każdego zadania powinno być programem komputerowym. Ten progam powinien
się budować poprzez system budowania CMake lub make na bossie. Jeśli w katalogu
głównym Waszego repozytorium znajduje się plik CMakeLists.txt, użyję systemu CMake,
jeśli nie - to systemu make.
Budowanie z CMake
Będę to robił mniej więcej tak:
$ mkdir -p build
$ cd build
$ cmake ..
$ make <kod_zadania>
Budowanie z make
Tu będzie nawet prościej:
$ make <kod_zadania>
Zadania
Każde zadanie polega na napisaniu programu komputerowego, który wczytuje z wejścia opis grafu, oblicza coś i wypisuje opis tego czegoś na wyjście. Format wejścia jest następujący
n m
u_1 v_1
u_2 v_2
...
u_m v_m
gdzie n i m oznaczają odpowiednio liczbę wierzchołków oraz krawędzi. u_i to
początki krawędzi, a v_i - ich końce. Wierzchołki są numerowane różnymi liczbami
całkowitymi od 1 do n.
Zadanie 1
Kod zadania: topo/sort
Wypisz na wyjście jakikolwiek z porządków topologicznych grafu. Jeśli nie ma, to wypisz NIE. Ograniczenia: n ≤ 200000, m ≤ 300000.
Zadanie 2
Kod zadania: topo/count
Wypisz na wyjście liczbę porządków topologicznych grafu. Ograniczenia: n ≤ 20.
Zadanie 3
Kod zadania: scc/partition
Wypisz n liczb całkowitych z zakresu 1...n. i-ta i j-ta powinny być równe wtedy
i tylko wtedy, gdy i oraz j są w jednej silnie spójnej składowej. Ograniczenia:
n ≤ 200000, m ≤ 300000.
Zadanie 3
Kod zadania: scc/make1
Dodaj do grafu jak najmniejszą liczbę krawędzi, tak żeby graf był silnie spójny.
Na wyjście wypisz liczbę dodanych krawędzi oraz, w kolejnych wierszach, końce
kolejnych krawędzi. Ograniczenia: n ≤ 200000, m ≤ 300000.