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

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


Timp maxim de execuţie / test:
0.3s
Memorie totala disponibilă / stivă:
2MB / 1MB

Domnul Z, profesorul de limba română de la clasa a IX-a a stabilit cu cei N elevi ai săi temele individuale de documentare şi cercetare, care au fost numerotate cu numere de la 1 la N. După realizarea temelor, acestea vor fi grupate în una sau mai multe reviste care vor participa la concursul revistelor şcolare. Regulamentul concursului prevede ca revista să fie compusă din teme care au elemente comune sau care se „potrivesc”; dacă tema A are elemente comune cu tema B, iar tema B are elemente comune cu tema C, atunci tema A se „potriveşte” cu tema C, astfel cele trei teme pot face parte din aceeaşi revistă.

Cerinţă

Cunoscând n numărul de elevi (implicit numărul de teme), M numărul de perechi de teme care au elemente comune şi temele care au elemente comune să se determine numărul minim de reviste care vor participa la concurs.

Date de intrare

Fişierul de intrare teme.in conţine pe prima linie numerele naturale N şi M separate prin câte un spaţiu. Pe următoarele M linii se află câte două numere naturale A B cu semnificaţia „tema A are elemente comune cu tema B”.

Date de ieşire

Fişierul de ieşire teme.out va conţine o singură linie pe care va fi scris un număr natural reprezentând numărul minim de reviste care se vor realiza.

Restricţii

1 ≤ N ≤ 300
1 ≤ A, B ≤ N
0 ≤ M ≤ 32000
• Perechile A B din fişierul de intrare sunt distincte.

Exemple

teme.inteme.outExplicaţii
6 4 1 2 2 3 4 5 4 6 2 Temele 1 şi 2 au elemente comune, la fel şi temele 2, 3 atunci 1 şi 3 se potrivesc , astfel temele 1, 2, 3 vor face parte din aceeaşi revistă.
temele 4 şi 5 au elemente comune, la fel şi temele 4, 6 atunci 5 şi 6 se potrivesc , astfel temele 4, 5, 6 vor face parte din aceeaşi revistă.
Numărul minim de reviste va fi 2.

autor: Prof. Lucia Miron
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
surse trimise | ajutor