Wstęp do Teorii Grafów

10.12.2009 - Kacper Król
Trudność

Zadania

 

Pług

Limit czasowy: 1s; Limit pamięciowy: 16MB;

Zbliża się zima i Stefana czekają ciężkie dni, bowiem jest kierowcą śnieżnego pługu. Robota lekką nie jest, a że Stefan nie jest w ciemię bity, to chciałby wcześniej zaplanować sobie pracę, tak by mieć więcej wolnego czasu. Wiadomo, że odśnieżyć trzeba każdą drogę, ale Stefan chciałby wiedzieć, czy może to zrobić w taki sposób, by nie jeździć po już odśnieżonych drogach. Znając plan połączeń pomiędzy skrzyżowaniami w mieście, pomóż Stefanowi by tym razem zima nie zaskoczyła drogowców. Wiemy, że Stefan pragnie wrócić na skrzyżowanie, z którego rozpoczął podróż.

Wejście:

Na wejściu podany jest opis dzielnicy, którą tym razem ma odśnieżyć Stefan. Opis składa się z par liczb $ m $, $ n $ $ \left(1 \leq m,n \leq 50\right) $, które oznaczają, że ze skrzyżowania o numerze $ m $ można dojechać do skrzyżowania o numerze $ n $ (i w drugą stronę).
Na koniec wejścia podane jest 0.

Wyjście:


Jeżeli w danej dzielnicy da się wyznaczyć trasę, o którą chodzi Stefanowi, to wypisz TAK. W przeciwnym przypadku wypisz NIE.

Przykład:

Wejście:

1 2
2 3
3 1
1 2
2 3
3 1
0

Wyjście:

TAK

 


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

Zenon

Limit czasowy: 1s; Limit pamięciowy: 16MB;

Zenon dołączył w grudniu do nowej klasy. Jak to zwykle bywa w takich sytuacjach, czuje się trochę nieswojo, gdyż nie zdążył jeszcze nikogo poznać. Integracje z klasą utrudnia mu fakt, że jest bardzo nieśmiały, ale za to jest dość błyskotliwy. Pomyślał, że jeśli pozna w klasie najpopularniejszą osobę, to dzięki takim kontaktom szybciej zintegruje się w nowej klasie, niż gdyby miał się zapoznać z każdym z uczniów. O popularności osoby $ A $ świadczy fakt, ile osób uważa ją za popularną. Jeżeli osoba $ B $ uważa osobę $ A $ za popularną to zapisujemy to jako parę $ A $ $ B $. Z tej okazji, że Ty już wiesz całkiem sporo o grafach, a Zenon jeszcze nie miał okazji ich poznać, to poprosił Cię o pomoc!


Wejście:


Na wejściu będzie podana liczba n oznaczająca liczbę par $ \left(1 \leq n \leq 1000\right) $. Dla ułatwienia, zamiast imion i nazwisk uczniów, będziemy używać ich numerów z dziennika. Osób w klasie będzie nie więcej niż $ 46 $.


Wyjście:


Na wyjściu musisz podać numer najpopularniejsze osoby w klasie. Jeżeli dwie osoby cieszą się taką samą popularnością, to podaj tę z nich, która ma niższy numer w dzienniku.


Przykład:

Wejście:


5
1 2
2 3
3 1
5 1
1 6


Wyjście:

 
1

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com