Deskripsi
Ada N siswa dalam satu kelas. Beberapa dari mereka adalah teman, sementara beberapa lainnya tidak. Persahabatan mereka bersifat transitif. Misalnya, jika A adalah teman langsung dari B, dan B adalah teman langsung dari C, maka A adalah teman tidak langsung dari C Dan kami mendefinisikan lingkaran pertemanan adalah sekelompok siswa yang merupakan teman langsung atau tidak langsung.
Diberikan matriks N*N M yang mewakili hubungan pertemanan antar siswa di kelas. Jika M[i][j] = 1, maka siswa ke-i dan ke-j adalah teman langsung satu sama lain, sebaliknya tidak. Dan Anda harus menampilkan jumlah lingkaran pertemanan di antara semua siswa.
Contoh 1:
Input: [[1,1,0], [1,1,0], [0,0,1]] Output: 2 Explanation:The 0th and 1st students are direct friends, so they are in a friend circle. The 2nd student himself is in a friend circle. So return 2.
Contoh 2:
Input: [[1,1,0], [1,1,1], [0,1,1]] Output: 1 Explanation:The 0th and 1st students are direct friends, the 1st and 2nd students are direct friends, so the 0th and 2nd students are indirect friends. All of them are in the same friend circle, so return 1.
Analisis
Friend Cycle merupakan permasalahan yang sangat klasik mengenai hubungan antar manusia. Secara umum, ketika berbicara tentang hubungan, kita akan langsung memikirkan struktur data grafik. Simpulnya adalah orang-orangnya dan ujungnya adalah hubungan. Mengenai grafik, pertama-tama kita harus mengetahui apakah grafiknya berarah atau tidak. Seperti pada soal ini persahabatan merupakan hubungan timbal balik, sehingga grafiknya tidak berarah, juga dapat kita peroleh dari matriks simetris.
Setelah kita memikirkan masalah ini dalam bentuk grafik, hidup menjadi lebih mudah, karena biasanya, kita akan menggunakan algoritma pencarian grafik seperti DFS dan BFS untuk menyelesaikan masalah grafik. Perbedaan terbesar antara algoritma pencarian pohon dan grafik adalah masalah lingkaran atau mengunjungi kembali, yang berarti kita memerlukan cara untuk menandai node sebagai telah dikunjungi untuk menghindari mengunjungi kembali. Dengan cara ini, kita dapat mengetahui bahwa soal ini mencoba mencari jumlah grafik yang terpisah.
Di sisi lain, kita dapat menganggap suatu masalah sebagai satu kelompok, seperti tetesan air, begitu ada hubungan antara dua tetes, maka keduanya akan menyatu menjadi lebih besar. Oleh karena itu, secara intuitif ini menjadi masalah pencarian gabungan yang lahir untuk menyelesaikan masalah penggabungan grafik.
Karena konsep SCC (Komponen Terhubung Kuat) mungkin terlintas di benak Anda, dan itu sangat masuk akal. Pada dasarnya, tujuan dari permasalahan ini adalah menemukan berapa banyak lingkaran di antara seluruh masyarakat dan SCC memodelkannya secara akurat. Kita pasti dapat menggunakan algoritma SCC yang kompleks untuk menyelesaikan masalah ini dan jika pertemanan bersifat satu arah, kita harus menggunakannya. Namun, dalam masalah ini, karena hubungannya bersifat bi-redirect, tidak akan ada tepian antara dua komponen. Jadi, kita cukup menerapkan algoritma pencarian grafik untuk menyelesaikannya.
Implementasi
Penelusuran Grafik
Kita mulai dengan setiap node yang belum dikunjungi dan memperluas grupnya, karena edge tidak berarah, setiap node yang terhubung akan dikunjungi dan mereka membentuk sebuah grup. Pada langkah ini, kita dapat menggunakan BSF atau DFS untuk melakukan ekstensi. Setelah melewati semua node, kita bisa mendapatkan semua grup.
Union-Find
Untuk Union-Find, cara tradisional adalah dengan mengekstrak tepi dari matriks, sehingga untuk setiap tepi, kita dapat menemukan induk dari node di setiap sisi dan kemudian melakukan operasi gabungan. Ada dua cara untuk melakukannya, pertama setiap kali terjadi penyatuan, kami akan memperbarui semua orang tua dalam salah satu grup, dan pada akhirnya, kami mendapatkan jumlah grup dengan menghitung indeks unik. Cara lainnya adalah dengan menginisialisasi nomor grup dengan jumlah node, setiap kali terjadi penggabungan berarti ada grup yang digabungkan, maka nomor grup kita kurangi 1, dalam prosesnya kita hanya perlu mengupdate induk yang paling banyak. indeks.
Kompleks
Penelusuran Grafik
Waktu: Karena kita hanya menyusuri tepian dan mengunjungi setiap node, seharusnya O(n)
Space : Kita memerlukan tempat untuk menyimpan informasi kunjungan, yaitu O(n)
Union-Find
Waktu: Untuk masing-masing sisi, kita perlu mencari orang tuanya dan melakukan penyatuan, yaitu O(mlogn)
Spasi: Spasi diperlukan untuk menyimpan informasi induk, O(n)
