EASY DSU C++
Intuition\nGraph nature is dynamic and we need to find maximum number of 1\'s which are connected so for this Brute forcre approach is to run a dfs over every n
# Intuition\nGraph nature is dynamic and we need to find maximum number of 1\'s which are connected so for this Brute forcre approach is to run a dfs over every node and find the count of connected components. Time complexity for this will be O(N^4).\n\nTo optimse this we can use DSU. first we will find union of all the connected one\'s. Then on every zero we will take sum of size[parents] of all components which can be connected through {i,j}. (As union will add all other componets and DSU will store Ultimate parent of all nodes and size will total number of children connected with that parent)\n\n# Approach\nWe will use DSU by size to implement it.\n\n1. we will find union of all the one\'s \n2. ans will be maximum of size array\n3. traverse in grid if grid[i][j]==0 we will store ultimate(root) parents of all the {x,y} which can be traverse through {i,j} and answer will size[i][j]\n4. to store in parent and size array we have used fromula i*n+j \n\n# Complexity\n- Time complexity:\nO(N2 * log(n))\n\n\n# Code\n```\nclass Solution {\npublic:\n    /* Dynamic graph -> so DSU  */\n    int Dparent[999999];\n    int Dsize[999999];\n\n    void DSU(int n){\n        for(int i=0;i<=n;i+=1){\n            Dparent[i]=i;\n            Dsize[i]=1;\n        }\n    }\n\n    int Dfind(int val){\n        if(val == Dparent[val]){\n            return val;\n        }\n\n        return Dparent[val]= Dfind(Dparent[val]);\n    }\n\n    void Dunion(int a,int b){\n        int pa= Dfind(a), pb=Dfind(b);\n\n        if(pa==pb){\n            return;\n        }\n\n        if(Dsize[pb]>Dsize[pa]) swap(a,b);\n\n        Dparent[pb]=pa;\n        Dsize[pa]+= Dsize[pb];\n    }\n\n    int largestIsland(vector<vector<int>>& grid) {\n        int n=grid.size();\n        int ele= n*n;\n        DSU(ele);\n\n        int dx[4]={1,-1,0,0};\n        int dy[4]={0,0,1,-1};\n\n        set<pair<int,int>> st;\n        int ans=0;\n        // Initialisation \n        for(int i=0;i<n;i+=1){\n            for(int j=0;j<n;j+=1){\n                if(grid[i][j]==1){\n                    int ele= i*n+j;\n                    for(int k=0;k<4;k+=1){\n                        int x= dx[k]+i;\n                        int y= dy[k]+j;\n\n                        if(x>=0 && y>=0 && x<n && y<n && grid[x][y]==1){\n                            int newele= x*n+y;\n                            Dunion(ele,newele);\n                        }\n                    }\n                }\n            }\n        }\n\n        for(int i=0;i<n*n;i+=1){\n            ans=max(ans,Dsize[i]);\n        }\n\n\n\n        // Now we can change maximum one zero to one in order to get answer\n        for(int i=0;i<n;i+=1){\n            for(int j=0;j<n;j+=1){\n                if(grid[i][j]==0){\n                    set<int> par;\n                    int ele= i*n+j;\n\n                    for(int k=0;k<4;k+=1){\n                        int x=dx[k]+i;\n                        int y=dy[k]+j;\n\n                        if(x>=0 && y>=0 && x<n && y<n && grid[x][y]==1){\n                            par.insert(Dfind(x*n+y));\n                        }\n                    }\n\n                    int an=1;\n                    for(auto it:par){\n                        an+= Dsize[it];\n                    }\n                    ans=max(ans,an);\n                }\n            }\n        }\n\n        return ans;\n\n    }\n};\n\n```\nPLEASEE UPVOTEE IF IT HELPED YOU
['Union Find', 'C++']