DAG to skrót od angielskich słów "directed acyclic graph". DAG to inaczej acykliczny graf skierowany. Dany jest dag G=(V,E) i liczba naturalna k. Zaproponuj algorytm, który znajduje parę wierzchołków (u,v), które można połączyć największą liczbą ścieżek o długości dokładnie k.
Dla grafu G = ({1,2,3,4},{(4,3),(3,1),(2,1),(4,2)} i k=2, taką parą jest (4,1). Istnieją 2 ścieżki długości 2 pomiędzy 4 i 1.
Napisz program który:
Wiersz 1: trzy liczby całkowite n, m, k oddzielone pojedynczymi znakami odstępu. Liczba n, to liczba wierzchołków w grafie, 2 <= n <= 50. Liczba m, to liczba krawędzi w grafie, 0 <= m <= n(n-1)/2. Liczba k, 0 <= k <= n-1, to długość interesujących nas ścieżek.
Każdy z kolejnych m wierszy zawiera jedną parę liczb u, v oddzielonych pojedynczym odstępem - (u,v) jest krawędzią w grafie.
Uwaga: wierzchołki są ponumerowane od 1 do n, w grafie nie ma krawędzi równoległych.
Jeśli w grafie nie ma ścieżek o zadanej długości, to jedno słowo brak.
W przeciwnym razie:
Dla danych wejściowych:
4 4 2 4 3 3 1 2 1 4 2
poprawnym wynikiem jest:
4 1 2
[Zgłoś rozwiązanie] [Moje zgłoszenia]