Union Find (Disjoint set)
Intuition\n Describe your first thoughts on how to solve this problem. \nFor a given grid of size (nxn), there can be (n+1)x(n+1) dots. We use union find(disjoi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFor a given grid of size (nxn), there can be (n+1)x(n+1) dots. We use union find(disjoint set) for these dots and get the desired reasult.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFor a cell, there will be 4 dots.\n\nFor example, let us take take the cell (0,0).\nThe top-left corner of the cell (0,0) is dot \'0\'.\nThe top-right corner of the cell (0,0) is dot \'1\'\nThe bottom-left corner of the cell (0,0) is dot \'4\'\nThe bottom-right corner of the cell (0,0) is dot \'5\'\n\n![leetcode_1.jpg](https://assets.leetcode.com/users/images/81313d6b-145b-4a5b-b0d9-770c92d3a4a3_1723261971.3050554.jpeg)\n\nAll boundary dots are connected to a virtual node (node 0). This ensures that any slashes on the boundary are treated appropriately, and any regions touching the boundary are considered connected to the outside.\n\nNow traverse through the grid, the union operations ensure that connected components are merged. After processing all cells, the count variable holds the number of regions formed by the slashes.\n\n\n# Complexity\n- Time complexity: O(n2) --> (traversing)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n2) -->  par.size=(n+1)*(n+1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass disjointset{\npublic:\n    vector<int>par,size;\n    int count=1;\n    disjointset (int n)\n    {\n        par.resize(n);\n        size.resize(n);\n\n        for(int i=0;i<n;i++)\n        {\n            par[i]=i;\n            size[i]=1;\n        }        \n    }\n\n    int findpar(int node)\n    {\n        if(node==par[node])return node;\n\n        return par[node]=findpar(par[node]);\n    }\n\n    void ubs(int u,int v)\n    {\n        int p1=findpar(u);\n        int p2=findpar(v);\n\n        if(p1==p2)\n        {\n            count++;\n            return;\n        }\n\n        if(size[p1]<size[p2])\n        {\n            par[p1]=p2;\n            size[p2]+=size[p1];\n        }\n        else\n        {\n            par[p2]=p1;\n            size[p1]+=size[p2];\n        }\n    }\n};\n\nclass Solution {\npublic:\n    int regionsBySlashes(vector<string>& grid) {\n        int n=grid.size();\n        int val=(n+1)*(n+1)+1;\n\n        disjointset ds(val);\n\n        for(int i=0;i<n+1;i++)\n        {\n            for(int j=0;j<n+1;j++)\n            {\n                if(i==0 || j==0 || i==n || j==n)\n                {\n                    int cellno=(i*(n+1))+j;\n                    if(cellno!=0)\n                    {\n                        ds.ubs(0,cellno);\n                    }\n                }\n            }\n        }\n\n        for(int i=0;i<n;i++)\n        {\n            for(int j=0;j<n;j++)\n            {\n                if(grid[i][j]==\'/\')\n                {\n                    int dot1= i * (n+1) + (j+1);\n                    int dot2= (i+1) * (n+1) + j;\n                    ds.ubs(dot1,dot2);\n                }\n                else if(grid[i][j]==\'\\\\\')\n                {\n                    int dot1= i * (n+1) + (j);\n                    int dot2= (i+1) * (n+1) + (j+1);\n                    ds.ubs(dot1,dot2);\n                }\n            }\n        }\n        return ds.count;\n    }\n};\n```
['Union Find', 'C++']