| Fișierul intrare/ieșire | matroid.in, matroid.out | Sursă | Baraj Shumen seniori 2014 |
|---|---|---|---|
| Autor | Cătălin Frâncu | Adăugată de |
Cătălin Frâncu
•
Catalin.Francu
|
| Timp de execuție pe test | 0.15 sec | Limită de memorie | 16384 KB |
| Scorul tău | N/A | Dificultate |
  2.75
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
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 ≤ 300.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
Pentru primul exemplu, animalul 1 poate fi supraviețuitor: 2 îl mănâncă pe 4, 1 pe 2, 1 pe 3. De asemenea, animalul 3 poate fi supraviețuitor: 3 îl mănâncă pe 4, 1 pe 2, 3 pe 1.
În al doilea exemplu, grădina zoologică nu poate fi redusă la un singur animal.
