Split every square into 2 parts + Union Find. [C++ beats 100%]
[For a better page layout, see this article on my blog: https://suzyz.github.io/2019/03/29/regions-cut-by-slashes/]\nWe split every square into two parts: the u
**[For a better page layout, see this article on my blog: https://suzyz.github.io/2019/03/29/regions-cut-by-slashes/]**\nWe split every square into two parts: the upper part and the lower part, and build a new graph.\nSquare (i, j) is now two nodes ```a = (i*n + j)*2 + 1``` and ```b = a + 1```.\nSorry that the picture is too big.\n![image](https://assets.leetcode.com/users/suzyzhang/image_1553504724.png)\n\nIf s[i][j] == \' \', then we connect a and b. Otherwise a and b shouldn\'t be connected.\nThen we need to connect square (i, j) with square (i + 1, j) and (i, j + 1).\n\nBetween (i, j) and (i + 1, j) : we only need to connect b to the upper part of (i + 1, j), which is ```a + 2 * n```.\n\nBetween (i, j) and (i + 1, j) : we connect the right part of (i, j) and the left part of (i + 1, j).\n\nAfter this, we can find the number of connected components of the new graph.\n\n\n**C++:**\n```\nclass Solution {\npublic:\n    vector<int> fa;\n    \n    int getfa(int x) {\n        if (x == fa[x])\n            return x;\n        fa[x] = getfa(fa[x]);\n        return fa[x];\n    }\n    \n    void unify(int x, int y) {\n        int a = getfa(x), b = getfa(y);\n        if (a != b)\n            fa[a] = b;\n    }\n    \n    int regionsBySlashes(vector<string>& g) {\n        int n = g.size();\n        int tot = n * n * 2;\n        \n        fa = vector<int>(tot+1);\n        for (int i = 1; i <= tot; ++i)\n            fa[i] = i;\n        \n        for (int i = 0; i < n; ++i)\n            for (int j = 0; j < n; ++j) {\n                int a = (i*n + j) * 2 + 1;\n                int b = a + 1;\n                \n                if (g[i][j] == \' \')\n                    unify(a, b);\n                \n                if (j < n-1) {\n                    int x = g[i][j] == \'/\' ? b : a;\n                    int y = g[i][j+1] == \'/\' ? b+1 : b+2;\n                    unify(x, y);\n                }\n                \n                if (i < n-1)\n                    unify(b, a + 2*n);\n            }\n        \n        int ans = 0;\n        for (int i = 1; i <= tot; ++i)\n            if (fa[i] == i)\n                ++ans;\n        \n        return ans;\n    }\n};\n```
[]