..."Μή μου τοὺς κύκλους τάραττε" είπε ο Αρχιμήδης στον Ρωμαίο στρατιώτη, ο οποίος τον βρήκε στην παραλία την ώρα που μελετούσε κάποιο Γεωμετρικό πρόβλημα γράφοντας στην άμμο. (πηγή : http://www.slideshare.net/Rebeka1586/ss-21175417 )
Πολύ γνωστή η παραπάνω φράση του Αρχιμήδη. Αυτό που είναι λιγότερο γνωστό είναι ότι ο Αρχιμηδης, χρησιμοποιώντας μια τεχνική βασισμένη στην προσέγγιση ενός κύκλου με κανονικά πολύγωνα, υπολόγισε κατώτερα και ανώτερα όρια για την τιμή του π τόσο κοντά στην πραγματική του τιμή, που το ρεκόρ προσέγγισης του π με άλλη μέθοδο (άπειρες σειρές) έσπασε το 1699, περίπου δύο χιλιετίες αργότερα!
Η ομάδα του Hellenico λοιπόν, μετά από πολύ συζήτηση, υποψιάζεται ότι ο Αρχιμίδης δεν έβρισκε πια ενδιαφέρον στη γεωμετρία, κι αποφάσισε να επεκταθεί και σε άλλους τομείς. Το πρόβλημα που προσπαθούσε να λύσει, εικάζουμε, δεν ήταν γεωμετρικό αλλά πρόβλημα θεωρίας γράφων. Συγκεκριμένα ήθελε να ξέρει αν ένας μη-κατευθυντικός γράφος περιέχει τουλάχιστον 2 κύκλους.
Περαιτέρω επεξήγηση
Ένας γράφος είναι ένα σύνολο από κυκλάκια (φανταστείτε τα σαν πόλεις) που ονομάζονται κόμβοι, και βελάκια (φανταστείτε τα σαν δρόμους που συνδέουν ορισμένες πόλεις) που ονομάζονται ακμές. Επειδή μια εικόνα είναι χίλιες λέξεις, ένας γράφος είναι αυτός : http://i.stack.imgur.com/mPzx7.gif
Ένας κύκλος είναι μία διαδρομή πάνω στον γράφο που ξεκινάει από έναν κόμβο, και μετά από κάποια βήματα, χωρίς να χρησιμοποιήσει κάποια ακμή δύο φορές (μπρος-πίσω) ξαναγυρνάει σε αυτό τον κόμβο. Στην παραπάνω περίπτωση υπάρχει ένας μόνο κύκλος, ο 1->2, 2->3, 3->1.
Προσέξτε ότι ένας γράφος δεν είναι αναγκαστικό να είναι συνδεδεμένος. Για παράδειγμα, κι αυτός είναι γράφος : http://support.sas.com/documentation/cdl/en/ornoaug/65289/HTML/default/images/concomp1.png
και περιέχει 2 κύκλους.
Στην πρώτη γραμμή δίνεται ένας αριθμός Τ, το πλήθος των γράφων που θα ακολουθήσουν.
Η περιγραφή κάθε γράφου γίνεται ως εξής. Αρχικά δίνονται δύο αριθμοί Ν και Μ, το πλήθος των κόμβων και το πλήθος των ακμών του γράφου.
Ακολουθούν Μ γραμμές, όπου η κάθε μία περιγράφει μία ακμή. Πιο συγκεκριμένα, η κάθε γραμμή περιέχει δύο θετικούς ακέραιους v-w, τους κόμβους που συνδέει η ακμή αυτή.
Το αρχείο εξόδου αποτελείται από Τ γραμμές.
Η i-οστή από αυτές τις γραμμές περιέχει το string "YES" αν ο i-οστός γράφος περιέχει τουλάχιστον 2 κύκλους, ενώ σε αντίθετη περίπτωση περιέχει την λέξη "NO".
1<=T<=20
1<=N<=50.000
1<=v,w<=N
(Άλλαξε η τελευταία γραμμή του input για λόγους σαφήνειας. Ήταν σωστό και πριν την αλλαγή όμως.) 3 6 6 1 2 2 3 3 1 4 5 5 6 6 4 6 7 1 2 2 3 3 1 3 4 4 5 5 6 6 4 4 4 1 2 2 4 1 3 1 4
YES YES NO
http://api.muchosmedia.com/brainwave/uploads/client_12/snap_bbbe84860082e1bacdeab44ffffc3cec.png