Union Find | Union by Rank | Faster than 87% | Easy to understand
\nclass Solution {\npublic:\n    vector<pair<int,int>>parent;\n    vector<int>csize;\n    int find_set(int a){\n        if(parent[a].first==a)\n            retu
```\nclass Solution {\npublic:\n    vector<pair<int,int>>parent;\n    vector<int>csize;\n    int find_set(int a){\n        if(parent[a].first==a)\n            return a;\n        return parent[a].first = find_set(parent[a].first);\n    }\n    void union_set(int a,int b){\n        a = find_set(a);\n        b = find_set(b);\n        if(a!=b){\n            if(parent[a].second == parent[b].second)\n                parent[a].second++;\n            if(parent[a].second < parent[b].second)\n                swap(a,b);\n            parent[b].first = a;\n            csize[a]+=csize[b];\n        }\n    }\n    int largestIsland(vector<vector<int>>& grid) {\n        int n=grid.size();\n        \n//         make set : provide unique identity to each cell i*n + j \n//         initialize cells having val 1 to size 1\n        for(int i=0;i<n*n;i++){\n//             first -> parent second->rank\n            parent.push_back({i,0});\n            csize.push_back(0);\n            if(grid[i/n][i%n])\n                csize[i]++;\n        }\n        \n//         union set all the cells with adjacent 1 if any (4 direction)\n        for(int i=0;i<n;i++){\n            for(int j=0;j<n;j++){\n                if(i+1<n and grid[i][j] and grid[i+1][j])\n                    union_set(i*n+j,(i+1)*n+j);\n                if(i-1>=0 and grid[i][j] and grid[i-1][j])\n                    union_set(i*n+j,(i-1)*n+j);\n                if(j+1<n and grid[i][j] and grid[i][j+1])\n                    union_set(i*n+j,i*n+j+1);\n                if(j-1>=0 and grid[i][j] and grid[i][j-1])\n                    union_set(i*n+j,i*n+j-1);\n            }\n        }\n        \n//        for each 0 valued cell, find adjacent cell\'s unique representative to add their size \n//         if 1 valued cell continue\n//         take into consideration no 0 cell case\n        unordered_set<int>dparent;\n        int ans = 0;\n        for(int i=0;i<n;i++){\n            for(int j=0;j<n;j++){\n                if(grid[i][j]){\n                    ans = max(ans,csize[i*n+j]);\n                    continue;\n                }\n                int cans = 1;\n                dparent.clear();\n                if(i+1<n and grid[i+1][j])\n                    dparent.insert(find_set((i+1)*n+j));\n                if(i-1>=0 and grid[i-1][j])\n                     dparent.insert(find_set((i-1)*n+j));\n                if(j+1<n and grid[i][j+1])\n                      dparent.insert(find_set(i*n+j+1));\n                if(j-1>=0 and grid[i][j-1])\n                     dparent.insert(find_set(i*n+j-1));\n                \n                for(int par:dparent){\n                    cans += csize[par];\n                }\n                ans = max(ans,cans);\n            }\n          }\n        \n            return ans;\n        }\n};\n```
['Union Find', 'C']