AtCoder Beginner Contest (177) - D - Friends

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 2.0s
Memory limit: 1G

Problem types
Allowed languages
C, C++, Java, Pascal, Python
Friends

Υπάρχουν N άτομα που τα ονομάζουμε Άτομο 1 μέχρι Άτομο N.

Σας δίνονται M γεγονότα του τύπου "Το Άτομο A_i και το Άτομο B_i είναι φίλοι." Το ίδιο γεγονός μπορεί να δοθεί πολλές φορές.

Αν ο X και ο Y είναι φίλοι, και ο Y και ο Z είναι φίλοι, τότε ο X και ο Z είναι επίσης φίλοι. Δεν υπάρχει φιλία που να μη μπορεί να προκύψει από τα M γεγονότα που μας δίνονται.

Ο κακός Takahashi θέλει να κατατάξει τα N αυτά άτομα σε κάποιο αριθμό ομάδων ώστε κάθε άτομο, να μην έχει φίλους στην ομάδα του.

Ποιος είναι ο ελάχιστος αριθμός ομάδων που χρειάζεται να δημιουργήσει;

Περιορισμοί
  • 2 \le N \le 2 \times 10^5
  • 0 \le M \le 2 \times 10^5
  • 1 \le A_i,B_i \le N
  • A_i \neq B_i
Είσοδος

Η είσοδος θα δίνεται από την τυπική είσοδο και θα έχει την ακόλουθη μορφή:

N M

A1 B1

⋮

AM BM
Έξοδος

Εκτυπώστε την απάντηση.

Παραδείγματα

1ο

input

5 3
1 2
3 4
5 1

output

3
Επεξήγηση πρώτου παραδείγματος:

Η διαίρεσή τους σε τρεις ομάδες {1, 3}, {2, 4}, και {5} επιτυγχάνει τον σκοπό του.


2ο

input

4 10
1 2
2 1
1 2
2 1
1 2
1 3
1 4
2 3
2 4
3 4

output

4

3ο

input

10 4
3 1
4 1
5 9
2 6

output

3

Comments

There are no comments at the moment.