B2 - Asociálne siete: AsociáliČasový limit: 2s, Pamäťový limit: 64MiBProgramovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3.4, Python 3.11Počet bodov: 1 [ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ] V dnešnom svete hrá Internet stále dôležitejšiu úlohu. A jeho neodmysliteľnou súčasťou sú dnes rôzne sociálne siete. Mnoho ľudí na nich trávi všetok voľný čas. No existuje aj početná skupinka, ktorá nemá o podobné služby záujem. A práve o týchto používateľov by chcela zabojovať nová firma, ktorá prichádza na trh s prvou asociálnou sieťou. Žiaľ, ich rozpočet nie je veľký a tak sa s mnohými problémami nevedia popasovať sami a potrebujú Tvoju pomoc. Prvý problém, s ktorým potrebujú pomôcť, sú štatistiky. Zaujímalo by ich, koľko skutočných asociálov je na ich sieti. Skutočného asociála je možné spoznať podľa toho, že nemá žiadnych priateľov. Pomôž im ich nájsť. ÚlohaProgramátori asociálnej siete teraz tvrdo pracujú na optimalizácii databázy, takže poskytnúť Ti môžu len záznam, ako chronologicky vznikali a zanikali prepojenia medzi jednotlivými používateľmi siete. Pre jednoduchosť je každý používateľ očíslovaný prirodzeným číslom od 1 po N. Na začiatku neexistujú medzi používateľmi žiadne spojenia. Ďalej sú definované prepojenia medzi jednotlivými používateľmi. Všetky prepojenia sú pritom obojsmerné. Používatelia sa môžu medzi sebou prepojiť aj viacnásobne. V tom prípade medzi nimi vznikne viacnásobná väzba. Keď sa používateľ rozhodne, že už nechce byť prepojený s iným používateľom, môže väzbu zrušiť. Každá takáto akcia ma za následok zrušenie len jedinej väzby. Ak ich existuje viac a používateľ už vôbec nechce byť spojený, musí väzbu zrušiť toľkokrát, koľkokrát bola predtým vytvorená. Po spracovaní celého záznamu treba napísať počet používateľov, ktorí sú skutoční asociáli a teda namejú žiadnu, v tom momente existujúcu väzbu.VstupPrvý riadok vstupu obsahuje dve prirodzené čísla N a M oddelené medzerou. N je počet používateľov zaregistrovaných v systéme a M je počet záznamov. Ďalej nasleduje M riadkov, z ktorých každý obsahuje písmeno buď A alebo R a dve prirodzené čísla X a Y, 1 ≤ X < Y ≤ N, kde X a Y je dvojica používateľov, medzi ktorými sa vytvára alebo ruší väzba. O akú operáciu ide určuje písmeno na začiatku riadku. Písmeno A znamená pridanie väzby a písmeno R znamená jej odobratie. Vstup je vždy korektný, teda odobratie väzby môže byť v zázname len ak už taká väzba existuje.VýstupVýstupom má byť jediné celé číslo, počet asociálov zaregistrovaných v systéme.B11 ≤ N ≤ 100, 1 ≤ M ≤ 100B21 ≤ N ≤ 1 000 000 000, 1 ≤ M ≤ 10 000PríkladVstup:5 5 A 1 2 A 1 3 A 1 2 R 1 2 R 1 3 Výstup:3 Vysvetlenie:Medzi používateľmi 1-2 a 1-3 vznikli väzby, pričom medzi 1-2 až dve. Následne boli dve zrušené, takže zostala už len jedna väzba medzi 1-2. Keďže je dokopy 5 používateľov, traja z nich sú asociáli. |