.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » pamant

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
pamant


Timp maxim de execuţie / test:
0.8s
Memorie totala disponibilă / stivă:
32MB / 8MB

Pe pământul din apropierea localităţii Gheorgheni s-au întâlnit toţi copiii şi doresc organizarea unui joc mai deosebit. Copiii au fost numerotaţi de la 1 la N şi ştim care sunt prietenii fiecărui copil.
O echipă este un grup maximal de copii cu proprietatea că oricare ar fi copiii P şi Q din echipă, există un şir de copii C1, ... , Ck astfel încât P=C1, Q=Ck, şi oricare ar fi 1≤i<k, Ci este prieten cu Ci+1.
Fiecare echipă va primi un cod, egal cu cel mai mic număr de ordine al unui copil din echipa respectivă.
Dorim să aflăm care sunt copiii vulnerabili, adică acei copii care dacă ar fi eliminaţi ar duce la spargerea echipei sale în două sau mai multe echipe.

Cerinţă

Scrieţi un program care să identifice toate echipele formate conform regulilor de mai sus, precum şi care sunt copiii vulnerabili.

Date de intrare

Fişierul de intrare pamant.in conţine pe prima linie două numere naturale N şi M reprezentând numărul de copii şi respectiv numărul relaţiilor de prietenie. Următoarele M linii conţin câte două numere naturale distincte x şi y, cu semnificaţia că x şi y sunt numerele de ordine a doi copii în relaţie de prietenie.

Date de ieşire

• Prima linie a fişierului de ieşire pamant.out conţine o singură valoare naturală A, reprezentând numărul de echipe.
• A doua linie conţine A numere naturale separate prin câte un spaţiu reprezentând codurile echipelor, în ordine crescătoare.
• A treia linie conţine o valoare naturală B reprezentând numărul de copii vulnerabili.
• A patra linie conţine B valori naturale, separate prin câte un spaţiu, reprezentând numerele de ordine, scrise în ordine crescătoare, ale copiilor vulnerabili.

Restricţii

1 ≤ N ≤ 100.000
1 ≤ M ≤ 200000
• Relaţiile de prietenie sunt reciproce: dacă x este prieten cu y, atunci şi y este prieten cu x.
• Dacă x este prieten cu y şi y este prieten cu z nu înseamnă că x este prieten cu z.

Exemple

pamant.inpamant.outExplicaţii
10 7 1 2 2 8 4 6 3 5 3 10 5 10 5 7 4 1 3 4 9 2 2 5 Există 4 echipe şi anume:
- prima echipă: 1 2 8
- a doua echipă: 3 5 7 10
- a treia echipă: 4 6
- a patra echipă: 9
Există doi copii speciali şi anume 2 şi 5.

autor: Prof. Carmen Popescu
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2011: sport2, macheta, butoane, acces, mxl, segmente, tsunami, tort1, ec, ape, poligon4, stalpi2, furnici1, telecab, ikebana, posta, fotbal1, xmoto, radare, fagure, goe, papusa, taburet, joc17, mesaj3, zar1, joc16, talent, xy, arbore1, robot3, copii, hacker, terenuri3d, terenuri, expresie2, poteci, joc18
De acelaşi autor: light, sort, iepuras, pahare, turist, arthur, pento, cod2, game, ambigram, jokes, trecere, paianjen, zumzi, cifru3, pixy, triburi, culori1, cifre5, arc
Despre graf: gropi, tgv, matrice2, miniasm, picnic, mere, circuit, soldati, arce, conflicte, desen, robot, furtuna, net, cuvinte, excursie, cadere, pioni, reinvent, kreg, flood, croco, johnie, matrice, arthur, kimberley, ro, sol, caravane, bete, honest, police, pcod, zmeu, auto2, grazing, datorii, trafic, sponsori, monede1, apm, bile1, caini, masina1, bomboane, turn1, shgraf, paintball, program1, tgraf, kgb, algola, felinar, joc6, tric, homeless, promo, turism, casute, joc10, prieteni1, traseu, zapezi, litoral, lover, trip, garaj, ziduri, tv, pact, echipe1, vitale, spion, trasee, bcolor, scara2, lant, ab3, soc, team, gard, rsp, graf, mexc, dep, albinuta1, atac2, cabane, drumuri, tj, grade, jungla, lanterna, magic5, coment, urgenta, fazan, lanturi, cfr, site, traseu1, trmv, graphgame, minuni, telefon, ubergraf, carray, pestera, chei, arbgraf, war, fluviu, drumuri1, entries, ubuntzei, pack, fotbal1, dag, razboi, benzina2, wg, neconex, asfalt1, kubus2, module, progresii, dfs, prieteni3, megascoala, grafxy, dineu, vot1, biperm, drumuri2, nrgraf, cristal, cartite, copaci3, dragoni, nuclee
Despre conexitate: arce, flood, matrice, shgraf, trip, pact, echipe1, vitale, spion, bcolor, mexc, dep, fazan, cfr, chei, teme, entries, neconex, module, drumuri2, cristal, nuclee
surse trimise | ajutor