Lingkaran Pertemanan
Hitung banyaknya kelompok pertemanan dan ukuran kelompok terbesar.
Sebuah aplikasi pesan ingin mengelompokkan penggunanya. Dua orang berada di kelompok yang sama bila mereka berteman langsung, atau terhubung lewat rantai pertemanan.
Masukan
Baris pertama berisi N (1 sampai 10000) dan M (1 sampai 20000). Orang dinomori 1 sampai N. M baris berikutnya masing-masing berisi dua orang yang berteman.
Keluaran
Dua baris: Kelompok: X dan Terbesar: Y. Orang tanpa teman dihitung sebagai kelompok sendiri.
Contoh masukan dan keluaran
Contoh 1
Masukan
7 4 1 2 2 3 4 5 6 6
Keluaran
Kelompok: 4 Terbesar: 3
Petunjuk
Coba kerjakan dulu. Buka petunjuk satu per satu kalau kamu buntu.
Petunjuk 1
Struktur data Disjoint Set Union (DSU) menyimpan untuk setiap orang siapa wakil kelompoknya. Menggabungkan dua kelompok cukup dengan menyambungkan wakilnya.
Petunjuk 2
Saat mencari wakil, sambungkan setiap orang yang dilewati langsung ke wakil akhirnya. Teknik ini, path compression, membuat pencarian berikutnya hampir seketika.