Fişierul intrare/ieşire:victorie.in, victorie.outSursăAlgoritmiada 2015, Runda 2
AutorCosmin Silvestru NegruseriAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test0.35 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Victorie

Se dă un graf neorientat cu N noduri şi M muchii. Se numeşte ciclu de lungime K al grafului un lanţ format din nodurile X1, X2, X3, ..., XK+1, cu proprietatea că X1 = XK+1. Un ciclu este elementar dacă toate nodurile cu excepţia primului şi ultimului sunt distincte două câte două. Se cere să se afişeze toate nodurile care aparţin cel puţin unui ciclu elementar de lungime impara cu mai mult de un element.

Date de intrare

Fişierul de intrare victorie.in conţine pe prima linie două numere naturale N şi M, reprezentând numărul de noduri respectiv numărul de muchii ale grafului. Fiecare din următoarele M linii conţin câte două numere naturale x şi y reprezentând câte o muchie din graf.

Date de ieşire

Fişierul de ieşire victorie.out conţine pe prima linie un număr natural NR reprezentând numărul de noduri care aparţin cel puţin unui ciclu elementar de lungime impară. Pe cea de-a doua se vor găsi NR numere naturale in ordine crescatoare, reprezentând indicele nodurilor care au această proprietate.

Restricţii

  • 1 ≤ N ≤ 100.000
  • 1 ≤ M ≤ 300.000
  • Nodurile din graf sunt numerotate de la 1 la N.
  • O muchie poate avea ambele capete în acelaşi nod

Exemplu

victorie.invictorie.out
4 4
1 2
1 3
2 3
2 4
3
1 2 3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?