Tanya bilangan komponen yang disambungkan selepas mengalih keluar bucu daripada pokok

Pertanyaan berikut boleh digunakan untuk menentukan komponen bersambung yang tinggal selepas mengalihkan bucu pokok: Mula-mula pertimbangkan struktur pokok. Kemudian, setiap komponen yang disambungkan diperiksa dengan bergerak melalui pepohon menggunakan algoritma carian luas-dahulu atau mendalam-dahulukan. Setelah bucu yang diperlukan dikeluarkan, kaedah traversal yang sama digunakan untuk menentukan bilangan komponen yang disambungkan. Keputusan akan ditentukan berdasarkan perubahan dalam kiraan sebelum dan selepas pengusiran. Kaedah ini memantau perubahan sambungan dengan berkesan dan membantu dalam mengira kemas kini kepada komponen yang disambungkan dalam pepohon.

Kaedah penggunaan

• Kaedah Depth First Search (DFS).

• Dan semak undang-undang

Kaedah Depth First Search (DFS)

Dalam kaedah DFS, kami mula-mula melakukan traversal DFS daripada mana-mana nod yang dipilih dalam pepohon asal untuk mengira komponen yang disambungkan selepas mengalihkan bucu daripada pepohon. Semasa traversal ini, kami mengulangi setiap nod yang disambungkan, menandakan setiap nod sebagai dilawati dan menjejaki bilangan kali DFS digunakan. Kami melakukan traversal DFS baharu selepas memadamkan bucu yang ditentukan, memastikan bucu yang dipadamkan dilangkau semasa fasa penerokaan. Kami boleh menentukan bilangan komponen yang disambungkan dalam pepohon yang dikemas kini dengan membandingkan bilangan panggilan ke DFS sebelum dan selepas pemadaman. Kaedah ini boleh mengira bilangan elemen yang disambungkan dengan cekap semasa melaraskan perubahan dalam struktur pokok.

Algoritma

• Pilih mana-mana bucu pada pokok asal sebagai titik permulaan untuk traversal DFS.

• Tetapkan pembolehubah "kiraan" untuk mula mengira komponen yang disambungkan. Mula-mula, tetapkan kepada 0.

• Dari puncak permulaan yang dipilih, gunakan DFS untuk melintasi pokok.

• Tandai setiap bucu yang dilawati semasa traversal DFS dan tambahkan "kiraan" sebanyak 1 untuk setiap panggilan DFS baharu (iaitu, untuk setiap komponen yang disambungkan ditemui).

• Selepas traversal DFS selesai, bilangan elemen yang disambungkan dalam pokok asal akan diwakili oleh "count".

• Alih keluar bucu yang ditentukan daripada pokok.

• Ulangi traversal DFS dari bucu permulaan yang sama, pastikan untuk mengelak daripada meneroka bucu yang dipadamkan.

• Apabila menjalankan DFS, kemas kini pembolehubah "kiraan" sama seperti sebelumnya.

• Bilangan komponen yang berkaitan dalam pokok yang dinaik taraf akan ditentukan dengan menolak "kiraan" selepas pemindahan daripada "kiraan" permulaan.

Contoh

#include <iostream>
#include <vector>

void dfs(const std::vector<std::vector<int>>& tree, int v, 
std::vector<bool>& visited, int& count) {
   visited[v] = true;
   count++;
   for (int u : tree[v]) {
      if (!visited[u]) {
         dfs(tree, u, visited, count);
      }
   }
}

int countConnectedComponents(const std::vector<std::vector<int>>& tree, int startVertex) {
   int n = tree.size();
   std::vector<bool> visited(n, false);
   int count = 0;

   dfs(tree, startVertex, visited, count);
   return count;
}

int main() {
   std::vector<std::vector<int>> tree = {
      {1, 2},
      {0, 3},
      {0, 4},
      {1},
      {2}
   };

   int startVertex = 0;
   std::cout << countConnectedComponents(tree, startVertex) << std::endl;
   return 0;
}

Output

5

Dan semak kaedahnya

Kami mula-mula memulakan setiap bucu sebagai komponen berasingan dalam kaedah mencari kesatuan supaya kami boleh mengira komponen yang disambungkan selepas mengalih keluar bucu daripada pokok. Untuk menjejaki bahagian dan sambungan dalam pokok asal, kami mengambil dan mencari struktur data. Kami mengemas kini dan menanyakan struktur data untuk mencerminkan perubahan dalam sambungan pepohon selepas memadamkan puncak yang ditentukan. Kemudian kira dan semak bilangan set berbeza dalam struktur data. Kiraan yang terhasil mewakili ketersambungan komponen pokok yang dikemas kini. Selepas mengalih keluar bucu, kaedah carian boleh mengira komponen bersambung dengan cekap dan mengendalikan perubahan struktur dalam pokok dengan berkesan.

Algoritma

• Buat tatasusunan atau struktur data dari awal untuk mewakili setiap bucu sebagai bahagian pokok yang berbeza. Pada mulanya, setiap bucu ialah bucu induknya sendiri.

• Gunakan operasi carian DAN dalam langkah prapemprosesan untuk menentukan kiraan komponen bersambung bagi pokok asal.

• Gunakan struktur data kesatuan untuk menggabungkan bahagian pokok yang mengandungi bucu u dan v untuk setiap tepi (u, v). Kesambungan awal pokok diwujudkan dalam langkah ini.

• Alih keluar bucu yang ditentukan daripada pokok.

• Gunakan operasi carian kesatuan bagi langkah prapemprosesan pada pokok yang diubah suai.

• Selepas pemadaman, kira dan semak bilangan wakil ibu bapa yang berbeza dalam struktur data.

• Kiraan hasil mewakili ketersambungan komponen kemas kini pokok.

Contoh

#include <iostream>
#include <vector>

class UnionFind {
public:
   UnionFind(int n) {
      parent.resize(n);
      for (int i = 0; i < n; ++i) {
         parent[i] = i;
      }
   }

   int find(int u) {
      if (parent[u] != u) {
         parent[u] = find(parent[u]);
      }
      return parent[u];
   }

   void unite(int u, int v) {
      int rootU = find(u);
      int rootV = find(v);
      if (rootU != rootV) {
         parent[rootU] = rootV;
      }
   }

   int countDistinctParentRepresentatives() {
      int n = parent.size();
      std::vector<bool> distinct(n, false);
      for (int i = 0; i < n; ++i) {
         distinct[find(i)] = true;
      }
      int count = 0;
      for (bool isDistinct : distinct) {
         if (isDistinct) {
            count++;
         }
      }
      return count;
   }

private:
   std::vector<int> parent;
};

int main() {
   int n = 5;
   UnionFind uf(n);

   uf.unite(0, 1);
   uf.unite(0, 2);
   uf.unite(2, 3);
   uf.unite(2, 4);

   std::cout << uf.countDistinctParentRepresentatives() << 
std::endl;
   return 0;
}

Output

1

Kesimpulan

Ringkasnya, kaedah yang dibentangkan boleh mengira bilangan bahagian yang disambungkan dalam pokok dengan cekap selepas mengalihkan bucu tertentu. Perubahan ketersambungan dalam struktur pokok boleh dikendalikan dengan cekap menggunakan kaedah carian pertama mendalam (DFS) dan kaedah carian kesatuan. Kaedah DFS memulakan traversal dari puncak yang dipilih, menandakan setiap nod dilawati, dan mengira komponen yang disambungkan. Kiraan yang dikemas kini diperoleh dengan membandingkan kiraan traversal sebelum dan selepas selepas memadamkan bucu, dan traversal baharu dilakukan tanpa memasukkan nod yang dipadamkan.

Bilangan awal komponen yang disambungkan ditentukan menggunakan operasi kesatuan melalui kaedah Union-Find, yang memulakan setiap bucu sebagai komponen yang berasingan. Gunakan operasi kesatuan yang sama selepas memadamkan bucu dan kira wakil induk yang berbeza untuk mendapatkan kiraan yang dikemas kini.

Kedua-dua kaedah boleh memberikan cerapan berguna tentang keterkaitan pokok selepas bucu telah dialih keluar, dan sesuai untuk pelbagai senario.

Atas ialah kandungan terperinci Tanya bilangan komponen yang disambungkan selepas mengalih keluar bucu daripada pokok. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!