Καλησπέρα αφέντη Wayne.
Ο Joker και η συμμορία του πήγαν στο Black Hat USA 2017 όπου και έμαθαν τρόπο νέο να κάνουν ζημιά στη πόλη μας!
Συγκεκριμένα, αύριο βράδυ θα προσπαθήσουν να κάνουν ζημιά στις αντλίες νερού της Gotham με τη χρήση φυσαλίδων!
Οι φυσαλίδες προκαλούν διάβρωση στις αντλίες και μέσα σε μερικές ώρες θα τους κάνουν ζημιά με καταστροφικά αποτελέσματα!
Για να καταστρέψετε το σχέδιο του Joker, πρέπει να εκτός από το να τον σταματήσετε, να βεβαιωθείτε ότι το δίκτυο της πόλης δεν περιέχει κύκλους.
Αν προλάβει ο Joker να βάλει φυσαλίδες στο δίκτυο και μπουν σε κύκλο, θα κάνουν ζημιά σε εκείνη τη περιοχή παρόλο που θα έχετε ήδη συλλάβει τον Joker και την συμμορία του.
Δεδομένου του χάρτη με το σύστημα διανομής νερού, πρέπει να βεβαιωθείτε ότι ο χάρτης δεν έχει κύκλους.
Δεδομένα εισόδου
Στην πρώτη γραμμή υπάρχει ένας ακέραιος T, ο αριθμός των test cases που θα ακολουθήσουν.
Για κάθε test case, υπάρχουν 2 γραμμές εισόδου:
- Στην πρώτη γραμμή του test case, υπάρχουν 2 ακέραιοι
VκαιE, όπουVείναι ο αριθμός των κορυφών (vertices) καιEείναι ο αριθμός των ακμών (edges). - Στη δεύτερη γραμμή, υπάρχουν
Eζεύγη ακέραιων χωρισμένα με το κενό. Κάθε ζεύγος δείχνει τη διπλή κατεύθυνσης σύνδεση της κορυφήςAμε την κορυφήB.
Δεδομένα εξόδου
Για κάθε test case θα πρέπει να γράψετε μια γραμμή με ένα ακέραιο, στην περίπτωση που υπάρχει κύκλος θα γράψετε τον αριθμό 1 αλλιώς θα γράψετε τον αριθμό 0.
Περιορισμοί
1 ≤ T ≤ 1000
1 ≤ V ≤ 1000
1 ≤ E ≤ 10000
0 ≤ A,B ≤ V-1
Ο Βαγγέλης ο αρκούδος είναι ο άντρας-νυχτερίδα! (ή ο αρκούδος-νυχτερίδα για να είμαστε πιο σωστοί)
Υλικό ανάγνωσης
- https://en.wikipedia.org/wiki/Cycle_(graph_theory)
- https://el.wikipedia.org/wiki/Αναζήτηση_Κατά_Βάθος
- https://en.wikipedia.org/wiki/Cycle_detection
- https://www.blackhat.com/us-17/briefings/schedule/#evil-bubbles-or-how-to-deliver-attack-payload-via-the-physics-of-the-process-7689
Βοηθητικό υλικό
- Πρόγραμμα παραγωγής τυχαίων test cases – [download id=”3801″]
This post is also available in: Αγγλικα
