Mosty i punkty artykulacji

02.10.2010 - Michał Karpiński
TrudnośćTrudność

Zadanie ze sprawdzaczką

Poniżej znajdują się proste zadania do napisania na komputerze, które związane są z wyszukiwaniem mostów i punktów artykulacji. Zachęcam do sprawdzenia nabytej wiedzy w praktyce.

Zadanie 1 - "Grafy mostowo-silne"

Mamy dany graf nieskierowany. Przyjmijmy następujące definicje: most jest silny, jeśli na obu jego końcach znajdują się punkty artykulacji. Z drugiej strony most nazywamy słabym, jeśli tylko jeden (lub żaden) z jego końców jest punktem artykulacji. Graf mostowo-silny to taki, który zawiera więcej mostów silnych niż słabych. Zadaniem jest stwierdzić, czy podany graf jest mostowo-silny.

Wejście

W pierwszym wierszu podane są dwie liczby $ N $ i $ M $ oddzielone spacją (gdzie $ 0 \le N,M \le 100000 $). $ N $ oznacza liczbę wierzchołków, a $ M $ liczbę krawędzi w grafie. W następnych $ M $ liniach podane są połączenia między wierzchołkami zapisane w postaci $ a\hspace{3 mm} b $ co oznacza, że istnieje krawędź z wierzchołka $ a $ do wierzchołka $ b $ (pamiętamy, że graf wejściowy jest nieskierowany).

Wyjście

Odpowiedzią ma być jedna linia z napisem TAK, jeśli graf jest mostowo-silny lub NIE w przeciwnym wypadku.

Przykład 1

Wejście:
6 7
1 2
1 3
3 2
6 3
4 6
5 4
6 5

Wyjście:
TAK

Przykład 2

Wejście:
2 1
1 2

Wyjście:
NIE

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

Zadanie 2 - "K-długie-mosty"

K-długim-mostem nazywamy drogę prostą w grafie nieskierowanym, która złożona jest jedynie z $ k $ mostów. Zawsze rozpatrujemy najdłuższą taką drogę. Dla przykładu: na grafie obok znajduje się 1-długi-most, 3-długi-most i 4-długi-most. Zadaniem jest wyznaczenie wszystkich k-długich-mostów (dla dowolnego $ k $). Możesz założyć, że z każdego wierzchołka nie wychodzi więcej niż dwa mosty.

Wejście

W pierwszym wierszu podane są dwie liczby $ N $ i $ M $ oddzielone spacją (gdzie $ 0 \le N,M \le 100000 $). $ N $ oznacza liczbę wierzchołków, a $ M $ liczbę krawędzi w grafie. W następnych $ M $ liniach podane są połączenia między wierzchołkami zapisane w postaci $ a\hspace{3 mm} b $ co oznacza, że istnieje krawędź z wierzchołka $ a $ do wierzchołka $ b $.

Wyjście

Dla $ p $ różnych k-długich-mostów należy wypisać $ p $ wierszy postaci $ k\hspace{3 mm} l $ co oznacza, że w grafie znajduje się dokładnie $ l $ różnych k-długich-mostów. Wiersze mają być wypisane rosnąco w zależności od $ k $. Jeśli w grafie nie ma żadnych mostów, należy wypisać BRAK.

Przykład 1

Wejście:
16 18
1 2
2 3
3 4
2 4
4 5
5 6
6 7
7 8
8 10
8 11
9 10
9 7
11 12
12 13
13 14
14 15
15 16
16 14

Wyjście:
1 1
3 1
4 1

Przykład 2

Wejście:
7 7
1 2
2 3
3 4
3 5
5 2
5 6
6 7

Wyjście:
1 2
2 1

Przykład 3

Wejście:
4 3
1 2
2 3
3 4

Wyjście:
3 1

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
4.636365
Twoja ocena: Brak Ocena: 4.6 (11 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com