C++ में डिस्जॉइंट सेट का उपयोग करके द्वीपों की संख्या खोजना

समस्या विवरण

इस समस्या में, हमें एक 2D बाइनरी मैट्रिक्स दिया गया है। हमारा कार्य डिस्जॉइंट सेट का उपयोग करके द्वीपों की संख्या खोजना है।

द्वीप मैट्रिक्स में 1 या अधिक जुड़े 1 का समूह है।

उदाहरण

इनपुट

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

आउटपुट

3

व्याख्या

द्वीप हैं: bin₀₀ - bin₁₁, bin₁₃, bin₃₂

हल का दृष्टिकोण

बाइनरी मैट्रिक्स से द्वीप खोजने के लिए डिस्जॉइंट सेट डेटा संरचना का उपयोग करना। द्वीप गिनती खोजने के लिए, हम मैट्रिक्स को पार करेंगे और सभी आसन्न शीर्षों का यूनियन करेंगे, सभी 8 पड़ोसियों की जांच करके, यदि वे 1 हैं तो वर्तमान इंडेक्स का अपने पड़ोसी के साथ यूनियन करें। फिर मैट्रिक्स का दूसरा पार करें, और यदि किसी इंडेक्स पर मान 1 है, तो उसका प्रतिनिधि खोजें। यदि आवृत्ति 0 है, तो 1 बढ़ाएं।

C++ कार्यान्वयन

#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);
    
    // सभी 8 दिशाओं के लिए यूनियन करें
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (mat[i][j] == 0) continue;
            
            int idx = i * m + j;
            // 8 पड़ोसी
            int dr[] = {-1, -1, -1, 0, 0, 1, 1, 1};
            int dc[] = {-1, 0, 1, -1, 1, -1, 0, 1};
            
            for (int k = 0; k < 8; k++) {
                int ni = i + dr[k];
                int nj = j + dc[k];
                if (ni >= 0 && ni < n && nj >= 0 && nj < m && mat[ni][nj] == 1) {
                    dus->Union(idx, ni * m + nj);
                }
            }
        }
    }
    
    vector<int> count(n * m, 0);
    int islands = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (mat[i][j] == 1) {
                int x = dus->find(i * m + j);
                if (count[x] == 0) {
                    islands++;
                    count[x]++;
                }
            }
        }
    }
    return islands;
}

int main() {
    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 << "बाइनरी मैट्रिक्स में द्वीपों की संख्या है: " << findIslandCount(mat);
    return 0;
}

आउटपुट

बाइनरी मैट्रिक्स में द्वीपों की संख्या है: 4

जटिलता विश्लेषण

• समय जटिलता: O(N × M × α(N×M)) जहां α व्युत्क्रम एकरमैन फंक्शन है (लगभग स्थिर)
• स्पेस जटिलता: O(N × M)

नोट

यह कार्यान्वयन 8-दिशात्मक कनेक्टिविटी (विकर्ण सहित) मानता है। 4-दिशात्मक के लिए, केवल ऊपर, नीचे, बाएं, दाएं की जांच करें।