SOLUTION | DSU O(n*n)
\n\nclass DSU\n{\n    vectorrank , parent , size;\n    public:\n    DSU(int n)\n    {\n        size.resize(n+1 , 1);\n        rank.resize(n+1 , 0);\n        par
```\n\n```class DSU\n{\n    vector<int>rank , parent , size;\n    public:\n    DSU(int n)\n    {\n        size.resize(n+1 , 1);\n        rank.resize(n+1 , 0);\n        parent.resize(n+1);\n        for(int i = 0;i<=n;i++)\n        parent[i] = i;\n    }\n    int findpar(int node)\n    {\n        if(node == parent[node])return node;\n\n        return parent[node] = findpar(parent[node]);\n    }\n    void unionbyrank(int u , int v)\n    {\n        int p_u = findpar(u);\n        int p_v = findpar(v);\n        if(p_u == p_v) return ;\n        if(rank[p_u] > rank[p_v])\n        {\n            parent[p_v] = p_u;\n        }\n        else if(rank[p_v] > rank[p_u])\n        {\n            parent[p_u] = p_v;\n        }\n        else \n        {\n            parent[p_v] = p_u;\n            rank[p_u]++;\n        }\n    }\n    void unionbysize(int u , int v)\n    {\n        int p_u = findpar(u);\n        int p_v = findpar(v);\n        if(p_u == p_v) return ;\n        if(size[p_u] > size[p_v])\n        {\n            size[p_u] += size[p_v];\n            parent[p_v] = p_u;\n        }\n        else \n        {\n            size[p_v] += size[p_u];\n            parent[p_u] = p_v;\n        }\n    }\n};\nclass Solution {\npublic:\n    int largestIsland(vector<vector<int>>& grid) {\n        int n = grid.size();\n        DSU dsu(n*n);\n        int dc[] = {1 , 0 , 0 , -1};\n        int dr[] = {0 , -1 , 1 , 0};\n        for(int i = 0;i<n;i++)\n        {\n            for(int j = 0;j<n;j++)\n            {\n                int node = i*n + j;\n                if(grid[i][j] == 1)\n                {\n                    for(int k = 0;k<4;k++)\n                    {\n                        int next_i = i + dr[k];\n                        int next_j = j + dc[k];\n                        if(next_i < 0 || next_j < 0 || next_i >= n || next_j >= n) continue;\n                        if(grid[next_i][next_j] == 0) continue;\n                        int next_node = next_i*n + next_j;\n                        if(dsu.findpar(node) == dsu.findpar(next_node))\n                            continue;\n                        dsu.unionbyrank(node , next_node);\n                    }\n                }\n            }\n        }\n        int ans = 0 , maxi = 0;\n        unordered_map<int , int>mp;\n        for(int i = 0;i<n*n;i++)\n        {\n            mp[dsu.findpar(i)]++;\n        }\n        for(int i = 0;i<n;i++)\n        {\n            for(int j = 0;j<n;j++)\n            {\n                int count = 1;\n                unordered_set<int>s;\n                if(grid[i][j] == 0)\n                {\n                    for(int k = 0;k<4;k++)\n                    {\n                        int next_i = i + dr[k];\n                        int next_j = j + dc[k];\n                        if(next_i < 0|| next_j < 0|| next_i >= n|| next_j >= n) continue;\n                        if(grid[next_i][next_j] == 0) continue;\n                        int next_node = next_i*n + next_j;\n                        if(s.find(dsu.findpar(next_node)) != s.end()) continue;\n                        s.insert(dsu.findpar(next_node));\n                        count += mp[dsu.findpar(next_node)];\n                        \n                    }\n                }\n                ans = max(ans , count);\n            }\n        }\n        for(auto it:mp)\n            ans = max(ans , it.second);\n        return ans;\n    }\n};
['Array', 'Union Find', 'Matrix', 'C++']