[DFS] Sprawdzanie spójności grafu
Data zakończenia: 2024-01-30 23:59
Języki:
cpp
Limit czasu: 5.0 s
Limit pamięci: 10 MB
Limit rozmiaru rozwiązania: 30 kB
Problem
Sprawdzenie, czy dany graf (niezorientowany) jest spójny.
Wejście
W pierwszej linii liczba naturalna 0 < n <= 100 = liczba wierzchołków grafu (wierzchołki numerujemy kolejnymi liczbami naturalnymi 0,1,...n-1).
W drugiej linii liczba naturalna 0 <= m = liczba krawędzi grafu.
W kolejnych m liniach kolejne krawędzie w postaci par liczb z przedziału [0,n-1].
Wyjście - dwie możliwości
(1) Gdy graf jest spójny, napis 'graf spojny'.
(2) W przeciwnym wypadku, napis 'graf niespojny'.
Wskazówki
(1) Wczytaj graf jako tablicę list sąsiedztwa.
(2) Użyj przeglądania grafu w głąb.
Przykładowe wejście I
6
5
0 1
0 2
2 1
2 3
4 5
Wynik I
graf niespojny
Przykładowe wejście II
4
3
0 2
1 2
2 3
Wynik II
graf spojny
