Fişierul intrare/ieşire:pamant.in, pamant.outSursăONI 2011, clasele 11-12
AutorCarmen PopescuAdăugată degabitzish1Gabriel Bitis gabitzish1
Timp execuţie pe test0.25 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Pamant

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 ≤ 200.000
  • 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.
  • Se acordă 40% din punctaj pentru corectitudinea primelor două linii din fişierul de ieşire şi 60% pentru celelalte două linii.
  • Pentru 30% din teste N ≤ 1.000.

Exemplu

pamant.inpamant.out
10 7
1 2
2 8
4 6
3 5
3 10
5 10
5 7
4
1 3 4 9
2
2 5

Explicaţie

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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content