Atenție! Aceasta este o versiune veche a paginii., scrisă la 2014-11-09 15:35:52.
Revizia anterioară   Revizia următoare  

Fișierul intrare/ieșire matroid.in, matroid.out Sursă Baraj Shumen seniori 2014
Autor Cătălin Frâncu Adăugată de avatar Catalin.Francu Cătălin Frâncu Catalin.Francu
Timp de execuție pe test 0.5 sec Limită de memorie 16384 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
open book Poți vedea testele pentru această problemă accesând atașamentele .

Matroid

Grădina zoologică din satul Matroid a rămas fără bani. Directorul grădinii, pentru a face economie la hrană, s-a gândit să hrănească unele animale cu altele, până când în final rămâne cu un singur animal supraviețuitor. El primește o listă cu dieta animalelor și știe dacă un animal poate sau nu să mănânce alt animal. Ajutați-l pe director să afle care dintre animale ar putea fi supraviețuitorul final.

Grădina zoologică are N animale distincte. Directorul nu se pricepe la taxonomie, așa încât nu operează cu numele animalelor, ci cu numerele lor de ordine, cuprinse între 1 și N.

Date de intrare

Fișierul de intrare matroid.in conține pe prima linie două numere N M, unde N este numărul de animale, iar M este lungimea listei de informații despre dietă. Pe următoarele M linii se află câte o pereche de numere x y, cu semnificația că animalul x se poate hrăni cu animalul y.

Date de ieșire

În fișierul de ieșire matroid.out se va scrie, pe prima linie, numărul de animale care ar putea fi supraviețuitorul final. Pe următoarele linii se vor scrie numerele acestor animale, în ordine crescătoare, câte unul pe linie

Restricții

  • 1 ≤ N ≤ 100.000
  • 1 ≤ M ≤ 100.000

Exemplu

matroid.in matroid.out
4 5
1 2
1 3
3 4
2 4
3 1
2
1
3
4 2
1 2
3 4
0

Explicație

...

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii