Using Euler's Formula (V - E + F = 2)
Euler\'s formula: V - E + F = 2\nV: # Vertices\nE: # Edges\nF: # Faces\nhttps://en.wikipedia.org/wiki/Planar_graph#Euler\'s_formula\n\nV: Two ends of all slashe
Euler\'s formula: V - E + F = 2\nV: # Vertices\nE: # Edges\nF: # Faces\nhttps://en.wikipedia.org/wiki/Planar_graph#Euler\'s_formula\n\nV: Two ends of all slashes and 4 corners of the square.\nE: All slashes plus 4 sides of the square. Note that the sides of the square might be splitted to multiple egdes by vertices on them.\nF-1 should be what we return if all edges are connected.\nEg:\n![image](https://assets.leetcode.com/users/beexcited/image_1544985732.png)\nV = 7, E = 9 in this image.\n\nNeed to resolve the situation that more than one component appear on the plane, so Union Find is utilized to get the number of connected components.\nThen F -1 + # of ConnectedComponents - 1 is what we return.\nEg:\n![image](https://assets.leetcode.com/users/beexcited/image_1544986083.png)\nV = 6, E = 5, # of ConnectedComponents = 2 in this case.\n\n\n```\nclass Solution {\n    int[] id;\n    int cnct = 0;   // # of connections happend in UF\n    private int find(int i) {\n        while (i != id[i]) {\n            id[i] = id[id[i]];\n            i = id[i];\n        }\n        return i;\n    }\n    private void connect(int i, int j) {\n        i = find(i);\n        j = find(j);\n        if (i != j) {\n            id[i] = j;\n            cnct++;\n        }\n    }\n    public int regionsBySlashes(String[] grid) { \n        HashSet<Integer> points = new HashSet();\n        int edgePoints = 0;\n        int edge = 0;\n        int n = grid.length;\n\t\t// all points lie on a (n+1) * (n+1) grid: represented as integer i * (n+1) + j\n        id = new int[(n + 1) * (n + 1)];\n        for (int i = 0; i < (n+1)*(n+1); i++) {\n            id[i] = i;\n        }\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < n; j++) {\n                if (grid[i].charAt(j) == \' \') continue;\n                int index1 = -1, index2 = -1;\n                if (grid[i].charAt(j) == \'\\\\\') {\n                    index1 = i * (n+1) + j;\n                    index2 = (i+1) * (n+1) + j + 1;\n                } \n                if (grid[i].charAt(j) == \'/\') {\n                    index1 = i * (n+1) + j + 1;\n                    index2 = (i+1) * (n+1) + j;\n                } \n                points.add(index1);\n                points.add(index2);\n                connect(index1, index2);\n                edge++;\n            }\n        }\n\t\t\n\t\t// add four corners\n        points.add(0 * (n+1) + 0);\n        points.add(0 * (n+1) + n);\n        points.add(n * (n+1) + 0);\n        points.add(n * (n+1) + n);\n\t\t\n\t\t// figure out how many egdes on each side of square\n\t\t// for each side of square:  # edges = # vertices - 1\n\t\t// for all sides of square: #edges on 4 sides = # vertices on 4 sides (each corner counted twice) - 4\n        for (int p : points) {\n            if (p / (n+1) == 0) {edgePoints++; connect(p, 0);}\n            if (p / (n+1) == n) {edgePoints++; connect(p, 0);}\n            if (p % (n+1) == 0) {edgePoints++; connect(p, 0);}\n            if (p % (n+1) == n) {edgePoints++; connect(p, 0);}\n        }\n        edge += (edgePoints - 4);\n\t\t\n\t\t// F - 1 + #connectedcomponents - 1=  2 + E - V - 1 + #connectedcomponents -1\n        // F - 1  + #connectedcomponents - 1 =  2 + edge - points.size() - 1 + (points.size() - cnct) - 1 = edge - cnct\n        return edge - cnct;\n    }\n}\n```
[]