Bahagikan nod ke dalam bilangan maksimum kumpulan

2493. Bahagikan nod ke dalam bilangan maksimum kumpulan

Kesukaran: Hard

topik: carian lebar-pertama, kesatuan mencari, graf

anda diberi integer positif n mewakili bilangan nod dalam graf yang tidak diarahkan . Nod dilabel dari 1 hingga n.

Anda juga diberi tepi array integer 2D, di mana tepi [i] = [a _i , b _i ] menunjukkan bahawa terdapat bidirectional Edge antara nod A _i dan b _i . notis bahawa graf yang diberikan boleh diputuskan.

Bahagikan nod graf ke dalam kumpulan M ( 1-indeks ) seperti itu:

• setiap nod dalam graf adalah tepat satu kumpulan.
• untuk setiap pasangan nod dalam graf yang disambungkan oleh kelebihan [a i , b _{i i tergolong dalam kumpulan dengan indeks y, kemudian | y - x | = 1. kembali}
bilangan maksimum kumpulan (iaitu, maksimum m) ke mana anda boleh membahagikan nod

. Kembali

-1 jika mustahil untuk mengelompokkan nod dengan syarat-syarat yang diberikan . Contoh 1:

input: n = 6, tepi = [[1,2], [1,4], [1,5], [2,6], [2,3], [4,6] ]

• output: 4
• Penjelasan: seperti yang ditunjukkan dalam imej kita:
tambah nod 5 ke kumpulan pertama.
• tambah nod 1 ke kumpulan kedua.
  Tambah nod 2 dan 4 ke kumpulan ketiga.
  Tambah nod 3 dan 6 ke kumpulan keempat.
  kita dapat melihat bahawa setiap kelebihan berpuas hati.
  boleh ditunjukkan bahawa jika kita membuat kumpulan kelima dan memindahkan mana -mana nod dari kumpulan ketiga atau keempat, sekurang -kurangnya pada tepi tidak akan dipenuhi.
  Contoh 2:

input: n = 3, tepi = [[1,2], [2,3], [3,1]]

• output: -1
• Penjelasan: Jika kita menambah nod 1 ke kumpulan pertama, nod 2 ke kumpulan kedua, dan nod 3 ke kumpulan ketiga untuk memenuhi dua tepi pertama, kita dapat melihat bahawa kelebihan ketiga tidak akan dipenuhi .
boleh ditunjukkan bahawa tiada kumpulan yang mungkin.
• Kekangan:

1 & lt; = n & lt; = 500 1 & lt; = edges.length & lt; = 10

4

tepi [i] .length == 2
• ^{1 & lt; = a} i
, b
• i
& lt; = n
• 3 _{Terdapat satu kelebihan antara mana -mana sepasang simpul.}
Petunjuk:
• 1. Jika graf tidak bipartit, tidak mungkin untuk mengumpulkan nod.
  2. Perhatikan bahawa kita dapat menyelesaikan masalah bagi setiap komponen yang disambungkan secara bebas, dan jawapan terakhir akan menjadi jumlah maksimum bilangan kumpulan dalam setiap komponen.
  3. Akhirnya, untuk menyelesaikan masalah untuk setiap komponen yang disambungkan, kita dapat melihat bahawa jika bagi sesetengah nod V kita menetapkan kedudukannya untuk berada di kumpulan paling kiri, maka kita juga boleh menilai kedudukan setiap nod lain. Kedudukan itu adalah kedalaman nod dalam pokok BFS selepas rooting pada nod v.

  Penyelesaian:

  Masalah, "Bahagikan nod ke dalam bilangan maksimum kumpulan" , melibatkan menentukan bilangan maksimum kumpulan yang mana nod graf yang tidak diarahkan dapat dibahagikan, sehingga:

  1. setiap nod milik satu kumpulan yang tepat.
  2. nod bersebelahan berada dalam kumpulan yang indeksnya berbeza dengan tepat 1. Jika graf tidak bipartit, pengelompokan adalah mustahil, dan fungsi mesti kembali -1.

  mata utama

  • sifat graf: Grafik boleh diputuskan.
  • Pengesahan: Untuk setiap komponen yang disambungkan, periksa sama ada bipartit. Jika tidak, kembali -1.
  • sifat bipartit: penyelesaiannya melibatkan BFS untuk mengesahkan bipartiteness.
  • Union-Find: berguna untuk mengumpulkan komponen yang bersambung dengan cekap.

  Pendekatan

  1. preprocessing:

     • mewakili graf menggunakan senarai adjacency.
     • Gunakan kesatuan untuk mengenal pasti komponen yang disambungkan.

  2. bfs untuk mengesahkan bipartiteness:

     • Untuk setiap komponen yang disambungkan, gunakan BFS untuk menentukan sama ada bipartit.
     • Jika ia bukan bipartite, kembali -1.

  3. Kirakan kiraan kumpulan:

     • Bagi setiap komponen yang disambungkan, gunakan BFS untuk menentukan kedalaman maksimum, mewakili bilangan maksimum kumpulan.

  4. Gabungkan hasil:

     • jumlah kiraan kumpulan maksimum semua komponen bipartit.

  Plan

  1. Bina graf sebagai senarai adjacency.
  2. Gunakan kesatuan-mencari komponen yang disambungkan kumpulan.
  3. untuk setiap nod dalam graf:
     • Gunakan BFS untuk memeriksa sama ada graf adalah bipartit dan hitung kedalaman maksimum komponen tersebut.
  4. Kembalikan jumlah kedalaman semua komponen sebagai hasilnya. Jika mana -mana komponen bukan bipartit, kembali -1.

  mari kita melaksanakan penyelesaian ini dalam php: 2493. Bahagikan nod ke dalam bilangan maksimum kumpulan
  

  <?php /**
   * @param Integer $n
   * @param Integer[][] $edges
   * @return Integer
   */
  function magnificentSets($n, $edges) {
      ...
      ...
      ...
      /**
       * go to ./solution.php
       */
  }
  
  /**
   * @param $graph
   * @param $u
   * @return int
   */
  private function bfs($graph, $u) {
      ...
      ...
      ...
      /**
       * go to ./solution.php
       */
  }
  
  class UnionFind {
      /**
       * @var array
       */
      private $id;
      /**
       * @var array
       */
      private $rank;
  
      /**
       * @param $n
       */
      public function __construct($n) {
         ...
         ...
         ...
         /**
          * go to ./solution.php
          */
      }
  
      /**
       * @param $u
       * @param $v
       * @return void
       */
      public function unionByRank($u, $v) {
         ...
         ...
         ...
         /**
          * go to ./solution.php
          */
      }
  
      /**
       * @param $u
       * @return mixed
       */
      public function find($u) {
         ...
         ...
         ...
         /**
          * go to ./solution.php
          */
      }
  }
  
  
  // Example usage:
  $n = 6;
  $edges = [[1,2], [1,4], [1,5], [2,6], [2,3], [4,6]];
  echo maxGroups($n, $edges); // Output: 4
  
  $n = 3;
  $edges = [[1,2], [2,3], [3,1]];
  echo maxGroups($n, $edges); // Output: -1
  ?>
  

  Penjelasan:

  1. Kelas Union-Find

  kumpulan struktur kesatuan (disjoint set kesatuan) nod ke komponen yang bersambung dan melakukan dua tugas utama:

  • Cari: Kenal pasti akar komponen bersambung nod.
  • Union: Gabungkan dua komponen yang disambungkan berdasarkan pangkat.

  2. BFS untuk pemeriksaan bipartit dan pengiraan kedalaman

  • Pengesahan bipartit: Menggunakan BFS, berikan "warna" berselang dengan nod. Jika nod bersebelahan berkongsi warna yang sama, graf tidak bipartit.
  • Pengiraan kedalaman: Ukur kedalaman pokok BFS untuk menentukan bilangan maksimum kumpulan.

  3. Gabungkan hasil

  • Kirakan kedalaman maksimum untuk setiap komponen yang disambungkan.
  • Tambahkan kedalaman untuk semua komponen untuk menentukan hasilnya.

  Contoh Walkthrough

  Contoh 1

  input:
  

  $n = 6;  
  $edges = [[1,2], [1,4], [1,5], [2,6], [2,3], [4,6]];
  

  Langkah -langkah:
  Membina Senarai Adjacency:

     1 -> [2, 4, 5]
     2 -> [1, 3, 6]
     3 -> [2]
     4 -> [1, 6]
     5 -> [1]
     6 -> [2, 4]
  

  Gunakan BFS pada komponen yang disambungkan:
  1. Komponen 1: bipartite. Kedalaman max = 4.
  kedalaman jumlah di semua komponen: 4.
  output: 4

  Contoh 2

  input:

  
  

  Langkah -langkah:

  $n = 3;  
  $edges = [[1,2], [2,3], [3,1]];
  

  Membina Senarai Adjacency:

     1 -> [2, 3]
     2 -> [1, 3]
     3 -> [1, 2]
  

  Gunakan BFS:
  1. Komponen 1: bukan bipartite.
  output: -1
  kerumitan masa
  Pembinaan graf:
  • o (e) , di mana e adalah bilangan tepi.
  Union-find:
  • o (α (n)) , di mana n adalah bilangan nod ( Hampir malar kerana pemampatan jalan).
  bfs:
  • o (v e) , di mana v adalah bilangan simpang. Kompleks keseluruhan: (n e)
  output untuk contoh

  Pendekatan ini dengan cekap mengendalikan masalah pengumpulan dengan memanfaatkan BFS untuk pemeriksaan bipartiteness dan pengiraan kedalaman sambil menggunakan kesatuan untuk memudahkan pengurusan komponen. Penyelesaian mengendalikan kedua -dua graf yang disambungkan dan terputus.

  $n = 6;
  $edges = [[1,2], [1,4], [1,5], [2,6], [2,3], [4,6]];
  echo magnificentSets($n, $edges); // Output: 4
  
  $n = 3;
  $edges = [[1,2], [2,3], [3,1]];
  echo magnificentSets($n, $edges); // Output: -1
  

  Pautan kenalan

  Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberikan repositori

  bintang di GitHub atau berkongsi jawatan di rangkaian sosial kegemaran anda? Sokongan anda sangat bermakna bagi saya!

  Jika anda mahukan kandungan yang lebih berguna seperti ini, jangan ragu untuk mengikuti saya:

  LinkedIn
  • github

Atas ialah kandungan terperinci Bahagikan nod ke dalam bilangan maksimum kumpulan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!