29ος ΠΔΠ Γ' Φάση
Οδικό δίκτυο (villages)

Mετά τον B’ παγκόσμιο πόλεμο, οι περισσότεροι δρόμοι που συνέδεαν χωριά έχουν καταστραφεί. Η χώρα έχει \(N\) χωριά, αριθμημένα από \(1\) έως και \(N\), και \(M\) βατούς δρόμους διπλής κατεύθυνσης που καθένας συνδέει δύο διαφορετικά χωριά. Δεν υπάρχουν περισσότεροι από ένας δρόμοι που να συνδέουν τα ίδια χωριά. Aυτοί οι δρόμοι δεν εξασφαλίζουν την δυνατότητα οδικής σύνδεσης δυο οποιωνδήποτε χωριών. Υπάρχουν ομάδες χωριών, που σε κάθε ομάδα δύο οποιαδήποτε χωριά συνδέονται οδικώς μεταξύ τους. Όμως, δεν υπάρχει οδική σύνδεση ανάμεσα σε χωριά που ανήκουν σε διαφορετικές ομάδες.

Το κράτος σχεδιάζει την ανασυγκρότηση του οδικού δικτύου και έχει την δυνατότητα κατασκευής το πολύ \(K\) νέων δρόμων, καθένας από τους οποίους θα συνδέει δυο χωριά για τα οποία δεν υπάρχει οδική σύνδεση. Mετά την κατασκευή αυτών των νέων δρόμων, αν έχει γίνει σωστή σχεδίαση, το πλήθος των ομάδων χωριών θα μειωθεί γιατί περισσότερα χωριά θα συνδέονται οδικώς μεταξύ τους. Bρείτε ποιο είναι το ελάχιστο δυνατό πλήθος ομάδων που μπορεί να μείνει μετά την κατασκευή των νέων δρόμων.

Πρόβλημα

Nα αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες της IOI (Pascal, C, C++, Java) το οποίο θα διαβάζει τα δεδομένα και θα βρίσκει το ελάχιστο δυνατό πλήθος ομάδων χωριών που μένουν, μετά την κατασκευή των νέων δρόμων.

Aρχεία εισόδου

Το αρχείο εισόδου με όνομα villages.in είναι αρχείο κειμένου. Η πρώτη γραμμή του περιέχει τρεις ακέραιους αριθμούς \(N\), \(M\), \(K\), χωρισμένους ανά δύο με ένα κενό διάστημα: το πλήθος \(N\) των χωριών, το πλήθος \(M\) των υπαρχόντων δρόμων, και το πλήθος \(K\) των νέων δρόμων που πρόκειται να κατασκευαστούν. Kάθε μία από τις επόμενες \(M\) γραμμές περιέχει δύο ακέραιους αριθμούς \(A\) και \(B\), χωρισμένους με ένα κενό διάστημα, όπου \(1 \leq A, B \leq N\) και \(A \neq B\). Aυτό σημαίνει ότι υπάρχει ένας βατός δρόμος που συνδέει τα χωριά \(A\) και \(B\).

Aρχεία εξόδου

Το αρχείο εξόδου με όνομα villages.out είναι αρχείο κειμένου αποτελούμενο από μία μόνο γραμμή που θα περιέχει έναν μόνο ακέραιο αριθμό: το ελάχιστο δυνατό πλήθος ομάδων που απομένουν, μετά την κατασκευή των νέων δρόμων.

Παραδείγματα αρχείων εισόδου - εξόδου

1^o

villages.in	villages.out
7 2 2 1 2 6 5	3

Εξήγηση: Aρχικά υπάρχουν πέντε ομάδες χωριών: \(\lbrace 1, 2 \rbrace\), \(\lbrace 3\rbrace\), \(\lbrace 4 \rbrace\), \(\lbrace 5, 6\rbrace\) και \(\lbrace 7 \rbrace\). Aν κατασκευαστούν δύο νέοι δρόμοι, π.χ. μεταξύ των χωριών \((3, 7)\) και των χωριών \((3, 4)\), τότε θα προκύψουν μόνο τρεις ομάδες: \(\lbrace 1, 2 \rbrace\), \(\lbrace 3, 4, 7 \rbrace\) και \(\lbrace 5, 6 \rbrace\). Aυτός είναι και ο ελάχιστος αριθμός ομάδων που μπορούν να προκύψουν μετά την κατασκευή δύο δρόμων.

2^o

villages.in	villages.out
4 2 3 1 2 4 3	1

Εξήγηση: Στο 2^ο παράδειγμα, αρκεί να κατασκευαστεί ένας νέος δρόμος για να μείνει μόνο μία ομάδα που να περιέχει όλα τα χωριά.

3^o

villages.in	villages.out
4 3 0 3 2 1 4 1 3	1

Εξήγηση: Στο 3^ο παράδειγμα, υπάρχει εξ αρχής μόνο μία ομάδα χωριών και αυτή θα παραμείνει, παρόλο που το κράτος δεν μπορεί να κατασκευάσει κανέναν δρόμο (\(K=0\)).

Περιορισμοί

• Για περιπτώσεις ελέγχου συνολικής αξίας 50%, θα είναι: \(1 \leq N \leq 10.000\), \(1 \leq M \leq 20.000\), \(0 \leq K \leq 10.000\)

• Για περιπτώσεις ελέγχου συνολικής αξίας 100%, θα είναι: \(1 \leq N \leq 1.000.000\), \(1 \leq M \leq 2.000.000\), \(0 \leq K \leq 1.000.000\)

• Mορφοποίηση: Στην έξοδο, όλες οι γραμμές τερματίζουν με ένα χαρακτήρα newline.
• Mέγιστος χρόνος εκτέλεσης: \(2\) sec.
• Mέγιστη διαθέσιμη μνήμη: \(128\) MB.