Táto úloha je programátorská. Ako svoje riešenie odovzdaj program vo svojom obľúbenom jazyku a automaticky sa dozvieš, koľko si dostal(a) bodov. Ak si takýto typ úloh ešte nikdy neriešil(a), skús sa pozrieť, ako by mal vyzerať ideálny program. Ak zatiaľ programovať nevieš, ale chcel(a) by si sa naučiť, môžeš skúsiť našu KSP School.
Ak máš hocijaké otázky k tejto úlohe, napíš Štepimu na [email protected].
Vedeli ste, že {insert_name} a {insert_name} spolu chodia? Ja som sa to dozvedel včera od Lucky, ktorej to povedala Sonička. A odkiaľ to vie Sonička? No, to už nikto nevie, klebety v Trojstene sa totiž šíria príliš rýchlo na to, aby to niekto stíhal sledovať.
Šírenie klebiet v Trojstene funguje tak, že vždy, keď niekto zistí nejakú klebetu, tak ju povie všetkým svojim kamarátom. Tí, keď sa to dozvedia, tak to povedia všetkým svojim kamarátom, a tak ďalej.
Nedávno som sa dozvedel jednu veľmi exkluzívnu klebetu a zaujímalo by ma, koľko ľudí sa ju dozvie, keď ju teraz začnem šíriť.
Ľudí v Trojstene si môžeme očíslovať $1$ až $n$. Na vstupe je zadaný počet ľudí $n$, počet kamarátstiev, a číslo, u koho sa klebeta na začiatku objaví.
Potom je na každom riadku popísané jedno kamarátstvo: dve čísla, ktoré znamenajú, že sa títo ľudia kamarátia. Kamarátstva sú vzájomné.
Zisti, ku koľkým ľuďom sa klebeta dostane.
Sú 4 sady vstupov, za každú je 25 bodov. V jednotlivých sadách:
| sada | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| počet ľudí $\leq$ | $10$ | $100$ | $1000$ | $100\,000$ |
| počet kamarátstiev $\leq$ | $20$ | $1000$ | $10\,000$ | $300\,000$ |
5 3 1
1 2
2 3
4 5
3
Máme $5$ ľudí, $3$ kamarátstva a klebeta začína u človeka $1$. Ten ju povie $2$-ke, tá ju povie $3$-ke, a potom sa už nemá kam ďalej šíriť.
4 3 3
1 2
2 4
4 1
1
Tentokrát sa mimo $3$ kamarátia všetci navzájom, ale $3$ sa nekamaráti s nikým, takže klebeta sa ku nikomu inému nedostane.
Vzoráky z tohto kola si môžeš pozrieť aj ako video
Každý, kto sa dozvie klebetu, tak o nej povie všetkým svojím kamarátom, takže tí sa to dozvedia tiež. Môžeme si teda pre každého človeka pamätať zoznam jeho kamarátov a mať funkciu, ktorá spraví, že keď sa niekto dozvie klebetu, tak ju rozpošle všetkým ostatným (teda zavolá tú istú funkciu pre každého svojho kamaráta). Ale rozpošle ju len, keď sa ju dozvie prvýkrát, inak by si posielali tú istú klebetu donekonečna, takže ešte si musíme pamätať, kto už klebetu vie, a vtedy ju ďalej neposielať.
# aby mohla funkcia volat sama seba dost vela krat
from sys import setrecursionlimit
setrecursionlimit(1_000_000)
pocet_ludi, pocet_kamaratstiev, zaciatok = map(int, input().split())
# kamarati[X] je zoznam kamaratov cloveka X
kamarati = [[] for _ in range(pocet_ludi)]
for _ in range(pocet_kamaratstiev):
# v zadani sa cisluje od 1, ale my chceme od 0
a, b = (int(i) - 1 for i in input().split())
kamarati[a].append(b)
kamarati[b].append(a)
# ti_co_vedia[X] je True, ak clovek X uz vie klebetu
ti_co_vedia = [False for _ in range(pocet_ludi)]
odpoved = 0
def dozvie_sa(clovek):
global odpoved
if ti_co_vedia[clovek]: return
ti_co_vedia[clovek] = True
odpoved += 1
for kamarat in kamarati[clovek]:
dozvie_sa(kamarat)
# cislujeme od 0
dozvie_sa(zaciatok - 1)
print(odpoved)