Zadanie
Ak nevieš programovať, nezúfaj! Môžeš sa to naučiť a ešte za to získať body, ktoré sa ti budú počítať namiesto tejto úlohy.
Stačí, že pôjdeš na stránku Programátorskej Liahne (liahen.ksp.sk). Keď budeš riešiť sadu conditions_cpp, bodmi, ktoré získaš si môžeš nahradiť riešenie tejto úlohy. Stačí ak na spodku tejto stránky odovzdáš pdf-ko s prezývkou, ktorú používaš na Liahni.
Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Jitke na [email protected]
Za siedmimi horami a siedmimi dolinami, v ďalekej krajine menom Trojsten sa chystajú prezidentské voľby. Kampane kandidátov sú v plnom prúde, no Emovi sa nepáči volebný program ani jedného z nich. Rozhodol sa teda sám vsúpiť do tohto kolotoču ako vhodný adept. No ak sa chce stať prezidentom, má pred sebou ešte dlhú cestu. Musí pozbierať dostatočný počet podpisov, aby mohol vôbec kandidovať a následne voľby vyhrať.
V Trojstene majú prezidentské voľby jednoduché pravidlá. Kandidát sa stane prezidentom ak sa pozná s každým občanom. Emo by rád vedel, či pozná každého občana, no má plné ruky práce so zháňaním podpisov. Pomôžte mu a zistite to preňho.
Úloha
Vašou úlohou je napísať program, ktorý na vstupe dostane zozmam známostí v Trojstene a zistí, či sa Emo pozná s každým občanom. Občan (aj Emo je občanom) sa s niekým pozná ak sa poznajú priamo alebo ob jedného človeka. Teda ak Emo pozná Andreja a Andrej pozná Timku, tak môžeme povedať, že aj Emo pozná Timku. Ak však Timka pozná Gabiku, ktorá inak nikoho iného nepozná, tak Emo Gabiku nepozná, pretože je to príliš vzdialená známosť.
Formát vstupu
Na prvom riadku vstupu sú tri celé čísla \(n\), \(m\) a \(e\). Číslo \(n\) (\(1 \leq n \leq 80\,000\)) je počet občanov Trojstenu, ktorí sú pre jednoduchosť očíslovaní od 1 po \(n\), číslo \(m (0 \leq m \leq 100\,000)\) je počet známostí a číslo \(e\) (\(1 \leq e \leq n\)) hovorí, ktorý občan je Emo.
Nasleduje \(m\) riadkov popisujúcich jednotlivé známosti. Na každom sú dve celé čísla \(a\), \(b\) (\(1 \leq a < b \leq n\)), ktoré udávajú, že občan s číslom \(a\) a občan s číslom \(b\) sa navzájom poznajú.
Formát výstupu
Na výstup vypíšte do jedného riadku slovo Ano ak sa Emo stane prezidentom alebo slovo Nie ak sa ním nestane. Do druhého riadku vypíšte vzostupne čísla občanov, ktorých Emo nepozná, oddelených medzerou. Ak pozná každého, do druhého riadku nevypisujte nič.
Hodnotenie
| Číslo sady | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| maximálne \(n\) | \(20\) | \(70\) | \(80\,000\) | \(80\,000\) | \(80\,000\) |
| maximálne \(m\) | \(100\) | \(1\,000\) | \(100\,000\) | \(100\,000\) | \(100\,000\) |
Príklady
Input:
5 5 1
1 2
1 3
1 4
2 3
2 5Output:
AnoEma označuje číslo \(1\). Priamo pozná \(2, 3, 4\). Občana \(5\) pozná skrz občana \(2\).
Input:
6 5 2
1 2
3 6
3 4
2 3
2 5Output:
AnoEma označuje číslo \(2\). Priamo pozná občanov \(1, 3, 5\). Občanov \(4, 6\) pozná skrz občana \(3\).
Input:
7 6 1
1 2
1 3
2 3
2 5
4 6
5 7Output:
Nie
4 6 7Ema označuje číslo \(1\). Priamo pozná občanov \(2, 3\). Občana \(5\) pozná skrz občana \(2\). Občania \(4\) a \(6\) sa poznajú len navzájom a Emo ich nepozná. Občan číslo 7 sa s Emom tiež nepozná, neexistuje totiž priamy známy Ema, ktorý by ho poznal.
Našou úlohou bolo zistiť, či sa Emo stane prezidentom. Na vstupe sme dostali zoznam známostí v Trojstene a overovali sme, s kým sa Emo pozná priamo alebo ob jedného človeka. Vždy sme teda určili, či sa Emo pozná s každým a ak nie, tak aj s kým sa nepozná.
Pomalšie riešenie
Otázou je, ako si zapamätať známosti, ktoré v Trojstene sú. Prvou možnosťou je použiť maticu susedností, ktorú budeme volať znamosti[][]. Je to dvojrozmerné pole, ktoré má toľko riadkov a stĺpcov, koľko je občanov Trojstenu. Každému občanovi patrí jeden riadok, v ktorom si v stĺpcoch pre každého ďalšieho občana pamätáme, či sa s ním pozná alebo nie. To znamená, že na pozícii znamosti[a][b] je hodnota 1, ak sa občan \(a\) pozná s občanom \(b\), inak je tam hodnota 0. Keď máme vytvorenú takúto prázdnu maticu, pridať nové známosti je jednoduché. Pridanie známosti medzi občanmi \(a\) a \(b\) znamená nastaviť hodnotu znamosti[a][b] a znamosti[b][a] na 1. No a nezabudneme si poznačiť, že Emo pozná aj Ema.
Ako pomocou tejto matice zistíme koho pozná Emo priamo a ob jedného človeka? Vytvorme si pole poznam[], kde si budeme o každom občanovi pamätať, či ho Emo pozná alebo nie.
Priame známosti sú jednoduché. Pozrieme sa na riadok reprezentujúci Ema v dvojrozmernom poli znamosti[][] a postupne ho celý prejdeme. Takto sa spýtame na každého občana, či má priamu známosť s Emom a ak má zapíšeme si to do poľa poznam[].
Emo pozná občana \(c\) ob jedného občana ak niekto, koho Emo pozná, pozná \(c\). Teda pre každého občana \(x\), o ktorom sme zistili, že ho Emo pozná sa teda pozrieme na \(x\)-tý riadok matice znamosti[x][], kde sú všetci ľudia, ktorých \(x\) pozná a aj tých si zaznačíme do poľa poznam[].
Nakoniec len prejdeme pole poznam[] a zistíme, či Emo pozná každého. Môžeme si vytvoriť pomocné pole nepoznam[], kam si prepíšeme občanov, ktorých Emo nepozná. Ak pozná všetkých ľudí, vypíšeme Ano, ak nie vypíšeme Nie a prechodom pola nepoznam[] vypíšeme občanov, ktorých nepozná.
Pole poznam[] má len \(n\) políčok a prechádzame ho konštatne veľa krát. Vybudovanie dvojrozmerného poľa znamosti[][] nám však bude trvať \(n \cdot n\) krokov, lebo pre každé políčko si musíme zaznačiť, či tá známosť existuje alebo nie a znamosti[][] majú \(n^2\) políčok. Časová zložitosť tohto riešenie je teda \(O(n^2)\). Najviac si pamätáme práve dvojrozmerné pole znamosti[][], teda aj pamäťová zložistosť bude \(O(n^2)\).
Vzorové riešenie
Predošlé riešenie je síce korektné, ale nie najrýchlejšie. Zamyslime sa, čo by sa dalo robiť lepšie oproti predchádzajúcemu riešeniu. V matici znamosti sme si pamätali všetko. Nás však zaujíma vzťah dvoch občanov iba ak sa poznajú, ak sa nepoznajú netreba nám to vedieť.
Prerobme si trochu dvojrozmerné pole znamosti na dvojrozmerný vektor. Vektor je pole, ktoré vie meniť veľkosť. Pre každého občana si budeme pamätať vektor občanov, ktorých priamo pozná. Tento spôsob zapamatania si vzťahov medzi občanmi sa nazýva zoznam susedov.
Zvyšok riešenia už je podobný ako v predošlom riešení. Vytvoríme si pole poznam, v ktorom si budeme pamätať koho Emo pozná. Najprv sem prepíšeme občanov, ktorých Emo pozná priamo zo znamosti. Samozrejme nezabudneme, že Emo pozná Ema. Následne pre každého nájdeného občana, ktorého Emo pozná priamo, zapíšeme do poznam občanov, ktorých on pozná priamo zo znamosti.
Nakoniec, rovnako ako v pomalšom riešení, len prejdeme pole poznam a zistíme, či Emo pozná každého. Môžeme si vytvoriť pomocný vektor nepoznam, kde si prepíšeme občanov, ktorých Emo nepozná. Ak je tento vektor prázdny, tak Emo pozná každého a vypíšeme Ano, ak nie vypíšeme Nie a vektor nepoznam.
Zapísaním známostí do zoznamu susedov sme výrazne zlepšili časovú aj pamäťovú zložitosť. Pole poznam sa nezmenilo a ani počet jeho prechodov, to nás teda neovplyvňuje. Znamosti sú však pole všetkých \(n\) občanov a pre každého si pamätáme len občanov, ktorých priamo pozná a nie tých, ktorých nepozná. To znamená, že každý vzťah zo zadania si pamätáme iba \(2\) krát. \(2\) krát kvôli tomu, že pri vzťahu \(a, b\), nielen občan \(a\) pozná občana \(b\), ale aj občan \(b\) pozná občana \(a\). Pamäťová zložitosť je teda \(O(n+2m)\). Časová zložitosť je rovnaká, lebo znamosti prejdeme konštantne veľa krát. V zložitostiach môžeme zanedbať konštanty, preto sa zložistosti zjednodušia na \(O(n + m)\).
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.