Fișierul intrare/ieșire pamant.in, pamant.out Sursă ONI 2011
Autor Carmen Popescu Adăugată de avatar Catalin.Francu Cătălin Frâncu Catalin.Francu
Timp de execuție pe test 0.3 sec Limită de memorie 12288 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty

Pământ

Notă: Această problemă este preluată de pe Campion și Infoarena.

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.

Exemplu

pamant.in pamant.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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii