C++ এ ডিসজয়েন্ট সেট ব্যবহার করে দ্বীপের সংখ্যা খুঁজুন

এই সমস্যায়, আমাদের একটি 2D বাইনারি ম্যাট্রিক্স দেওয়া হয়েছে। আমাদের কাজ হল DFS ব্যবহার করে দ্বীপের সংখ্যা খুঁজে বের করা .

দ্বীপ ম্যাট্রিক্সে 1 বা তার বেশি সংযুক্ত 1 এর গ্রাউন্ড।

সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,

ইনপুট

bin[][] = {{ 1 0 0 0}
   {0 1 0 1}
   {0 0 0 0}
   {0 0 1 0}}

আউটপুট

ব্যাখ্যা

Islands are :
   bin₀₀ - bin₁₁
   bin₁₃
   bin₃₂

সমাধান পদ্ধতি

একটি ডিসজয়েন্ট সেট ডেটা স্ট্রাকচার ব্যবহার করে একটি বাইনারি ম্যাট্রিক্স থেকে দ্বীপটি খুঁজে বের করতে। দ্বীপের গণনা খুঁজে বের করার জন্য, আমরা ম্যাট্রিক্স অতিক্রম করব এবং সমস্ত 8টি প্রতিবেশীকে পরীক্ষা করে সমস্ত সন্নিহিত শীর্ষবিন্দুর মিলন করব, যদি তারা 1 হয় তার প্রতিবেশীর সাথে বর্তমান সূচকের মিলন। তারপর ম্যাট্রিক্সের দ্বিতীয় ট্রাভার্সাল করুন, এবং যদি কোনো সূচকে মান 1 হয়, তাহলে এটির পাঠানো খুঁজুন। ফ্রিকোয়েন্সি 0 হলে, 1 এ বাড়ান।

উদাহরণ

আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,

#include <bits/stdc++.h>
using namespace std;
class DisjointUnionSets{
   vector<int> rank, parent;
   int n;
   public:
   DisjointUnionSets(int n){
      rank.resize(n);
      parent.resize(n);
      this->n = n;
      makeSet();
   }
   void makeSet(){
      for (int i = 0; i < n; i++)
      parent[i] = i;
   }
   int find(int x){
      if (parent[x] != x){
         return find(parent[x]);
      }
      return x;
   }
   void Union(int x, int y){
      int xRoot = find(x);
      int yRoot = find(y);
      if (xRoot == yRoot)
         return;
      if (rank[xRoot] < rank[yRoot])
         parent[xRoot] = yRoot;
      else if (rank[yRoot] < rank[xRoot])
         parent[yRoot] = xRoot;
      else {
         parent[yRoot] = xRoot;
         rank[xRoot] = rank[xRoot] + 1;
      }
   }
};
int findIslandCount(vector<vector<int>> mat){
   int n = mat.size();
   int m = mat[0].size();
   DisjointUnionSets *dus = new DisjointUnionSets(n * m);
   for (int j = 0; j < n; j++){
      for (int k = 0; k < m; k++){
         if (mat[j][k] == 0)
            continue;
         if (j + 1 < n && mat[j + 1][k] == 1)
            dus->Union(j * (m) + k, (j + 1) * (m) + k);
         if (j - 1 >= 0 && mat[j - 1][k] == 1)
            dus->Union(j * (m) + k, (j - 1) * (m) + k);
         if (k + 1 < m && mat[j][k + 1] == 1)
            dus->Union(j * (m) + k, (j) * (m) + k + 1);
         if (k - 1 >= 0 && mat[j][k - 1] == 1)
            dus->Union(j * (m) + k, (j) * (m) + k - 1);
         if (j + 1 < n && k + 1 < m && mat[j + 1][k + 1] == 1)
            dus->Union(j * (m) + k, (j + 1) * (m) + k + 1);
         if (j + 1 < n && k - 1 >= 0 && mat[j + 1][k - 1] == 1)
            dus->Union(j * m + k, (j + 1) * (m) + k - 1);
         if (j - 1 >= 0 && k + 1 < m && mat[j - 1][k + 1] == 1)
            dus->Union(j * m + k, (j - 1) * m + k + 1);
         if (j - 1 >= 0 && k - 1 >= 0 && mat[j - 1][k - 1] == 1)
            dus->Union(j * m + k, (j - 1) * m + k - 1);
      }
   }
   int *c = new int[n * m];
   int islands = 0;
   for (int j = 0; j < n; j++){
      for (int k = 0; k < m; k++){
         if (mat[j][k] == 1){
            int x = dus->find(j * m + k);
            if (c[x] == 0){
               islands++;
               c[x]++;
            }
            else
            c[x]++;
         }
      }
   }
   return islands;
}
int main(void){
   vector<vector<int>> mat = {
      {1, 1, 0, 1, 0},
      {0, 1, 0, 1, 1},
      {1, 0, 0, 1, 1},
      {0, 0, 0, 0, 0},
      {1, 1, 1, 0, 1}
   };
   cout<<"The number of islands in binary matrix is : "<<findIslandCount(mat);
}

আউটপুট

The number of islands in binary matrix is : 4