|
|
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`.
|
|
|
|
|
|
|
