JAVA - Union Find (explanation)
\n\n\n\n\n\n\n\n\n\n\n\n\nclass Solution {\n    int n;\n    public int regionsBySlashes(String[] grid) {\n        n = grid.length; // grid is NxN\n        \n   
![image](https://assets.leetcode.com/users/wcursino/image_1586606265.png)\n\n\n\n\n\n\n\n\n\n\n\n```\nclass Solution {\n    int n;\n    public int regionsBySlashes(String[] grid) {\n        n = grid.length; // grid is NxN\n        \n        UnionFind uf = new UnionFind(4 * n * n); // *Each site will have 4 regions\n        for(int i=0; i<n; i++){\n            for(int j=0; j<n; j++){\n                char c = grid[i].charAt(j);\n                // **Union the neighbors \n                // right side\n                if(j + 1 < n) uf.union(index(i, j, 2), index(i, j+1, 4));\n                \n                //top side\n                if(i -1 >= 0) uf.union(index(i, j, 1), index(i-1, j, 3));\n                \n                if(c == \'/\'){// *** union 1-2 and 3-4\n                    uf.union(index(i, j, 1), index(i, j, 4));\n                    uf.union(index(i, j, 3), index(i, j, 2));\n                }\n                \n                else if(c == \'\\\\\'){// **** union 1-4 and 2-3\n                    uf.union(index(i, j, 3), index(i, j, 4));\n                    uf.union(index(i, j, 1), index(i, j, 2));                    \n                }\n                \n                else if(c == \' \'){// **** union all 4\n                    uf.union(index(i, j, 1), index(i, j, 2));\n                    uf.union(index(i, j, 3), index(i, j, 4));\n                    uf.union(index(i, j, 4), index(i, j, 1));\n                }\n            }\n        }\n        return uf.roots;\n    }\n    \n    int index(int i, int j, int space){\n        return 4 * (n * i + j) + space - 1; \n    }\n    \n    class UnionFind{\n        int[] parent;\n        int[] size;\n        int roots;\n        UnionFind(int N){\n            parent = new int[N];\n            size = new int[N];\n            roots = N;\n            for(int i=0; i<N; i++){\n                parent[i] = i;\n                size[i] = 1;\n            }\n        }\n        int root(int i){\n            while(i != parent[i]){\n                parent[i] = parent[parent[i]]; // compress\n                i = parent[i];\n            }\n            return i;\n        }\n        void union(int p, int q){\n            int rootP = root(p);\n            int rootQ = root(q);\n            if(rootP == rootQ) return;\n            roots--;\n            if(size[rootP] < size[rootQ]){\n                parent[rootP] = rootQ;\n                size[rootQ] += size[rootP];\n            }else{\n                parent[rootQ] = rootP;\n                size[rootP] += size[rootQ];\n            }\n        }\n    }\n}\n```
[]