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