C1 - Asociálne siete: Trójsky kôňČ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 ] Tvorcovia prvej asociálnej siete narazili na ďalší pre nich neriešiteľný problém. Tentoraz sa ich systémom začal šíriť zákerný trójsky kôň. Funguje tak, že ak s napadnutým používateľom niekto vytvorí novú väzbu, automaticky sa nakazí a stáva sa tiež šíriteľom trójskeho koňa. Žiaľ, tvorcovia ho nevedia detekovať a tak chcú aspoň zistiť, koľko používateľov môže byť napadnutých. Ú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ť maximálny počet používateľov, ktorí môžu byť napadnutí zákerným trójskym koňom, ak na úplnom začiatku bolo napadnuté práve jedno konto.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, maximálny možný počet napadnutých používateľov.C11 ≤ N ≤ 100, 1 ≤ M ≤ 100C21 ≤ N ≤ 1 000 000 000, 1 ≤ M ≤ 1000PríkladVstup:5 6 A 1 2 A 1 3 A 1 2 R 1 2 R 1 3 A 3 4 Výstup:4 Vysvetlenie:Ak bolo napadnuté konto používateľa 1, tak postupne priamo infikoval používateľov 2 a 3. Používateľ 3 následne infikoval používateľa 4. |