C++ disjoint set or union find
This is a typical union find algorithm. merge all connected 1s into a group with the smallest index as the parent. Also add a size vector for the disjoint sets 
This is a typical union find algorithm. merge all connected 1s into a group with the smallest index as the parent. Also add a size vector for the disjoint sets and keep track of the max size.\n\nIterate all over the zeros and if we flip it and add all different set\'s length and update the max length.\n\nThe code is straightforward and easy to implement if we have the disjoint set toolbox.\nComplexity: O(N^2), 15ms\n\n```\nclass union_find\n{\n    int m,n;\n    int count;\n    vector<int> parent;\n    vector<int> size;\n    int max_size;\npublic:\n    union_find(vector<vector<int>>& grid)\n    {\n        count=0;\n        max_size=0;\n        m=grid.size(),n=grid[0].size();\n        parent.resize(m*n+1);\n        size.resize(m*n+1);\n        for(int i=0;i<m;i++)\n        {\n            for(int j=0;j<n;j++)\n            {\n                if(grid[i][j]) {parent[i*n+j]=i*n+j;size[i*n+j]=1;count++;}\n            }\n        }\n        if(count) max_size=1;\n        parent[n*m]=n*m;//dummy node\n    }\n    int find(int node)\n    {\n        while(parent[node]!=node) node=parent[node];\n        return node;\n    }\n    void merge(int ni,int nj)\n    {\n        int i_id=find(ni);\n        int j_id=find(nj);\n        if(i_id==j_id) return;\n        if(i_id<j_id) {parent[j_id]=i_id;size[i_id]+=size[j_id];size[j_id]=0;max_size=max(max_size,size[i_id]);}\n        else {parent[i_id]=j_id;size[j_id]+=size[i_id];size[i_id]=0;max_size=max(max_size,size[j_id]);}\n        count--;\n    }\n    bool connected(int ni,int nj) {return find(ni)==find(nj);}\n    int get_numset() {return count;}\n    int get_size(int p) {return size[p];}\n    int get_maxsize() {return max_size;}\n};\nclass Solution {\npublic:\n    int largestIsland(vector<vector<int>>& grid) {\n        //disjoint set and see which one flip will add the largest\n        //using the i*n+j as the root\n        //bfs search to merge \n        union_find uf(grid);\n        int m=grid.size(),n=grid[0].size();\n        int dir[][2]={{-1,0},{1,0},{0,-1},{0,1}};\n        for(int i=0;i<m;i++)\n        {\n            for(int j=0;j<n;j++)\n            {\n                if(grid[i][j])\n                {\n                    for(int k=0;k<4;k++)\n                    {\n                        int x=i+dir[k][0],y=j+dir[k][1];\n                        if(x>=0 && x<m && y>=0 && y<n && grid[x][y])\n                        {\n                            uf.merge(i*n+j,x*n+y);\n                        }\n                    }\n                }\n            }\n        }\n        //now we get all the adjoint set, we will check the 0 to see which connect two or three or 4\n        int maxlen=INT_MIN;\n        for(int i=0;i<m;i++)\n        {\n            for(int j=0;j<n;j++)\n            {\n                if(!grid[i][j])\n                {\n                    unordered_set<int> us;\n                    for(int k=0;k<4;k++)\n                    {\n                        int x=i+dir[k][0],y=j+dir[k][1];\n\n                        if(x>=0 && x<m && y>=0 && y<n && grid[x][y])\n                        {\n                            int p=uf.find(x*n+y);//same region cannot be added multiple times\n                            us.insert(p);\n                        }\n                    }\n                    int cnt=0;\n                    for(auto it=us.begin();it!=us.end();it++) cnt+=uf.get_size(*it);\n                    maxlen=max(maxlen,cnt);\n                }\n            }\n        }\n        return maxlen==INT_MIN?uf.get_maxsize():maxlen+1;\n    }\n};\n```
[]