UnionFind|DFS+ Euler Theorem V-E+F=2||Beats 100%
IntuitionThere is a theorem by Euler: for a connected planar graph( or a connected graph on a topological sphere),
V−E+F=2,(In general, 2 is replaced by χ(G)=2−
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
There is a theorem by Euler: for a connected planar graph( or a connected graph on a topological sphere),
$V-E+F=2$,(In general, 2 is replaced by $\chi(G)=2-2g$ where $g$=genus)
outside of the square there is 1 face. In this case ans=F-1.

2nd  approach uses DFS.
# Approach
<!-- Describe your approach to solving the problem. -->
[Please Turn on English subtitles if necessary]
[https://youtu.be/cR_D4uA3g3s?si=9dIX0sFQTQYwl1di](https://youtu.be/cR_D4uA3g3s?si=9dIX0sFQTQYwl1di)

1. How to set up the graph? Like playing Go, and set vertex on the crossings of lines.

2. Many other solutions use the dual graph of mine. The solutions here don't use any tricks for subdidiving a cell, but the formula for Euler-Theorem.

3. The graph may be disconnected, how to use it?
If graph is connected, number of components is 1. Since all components are inside of the boundary, it needs only adjusted by +(component-1)

4. All implementation here is using the following formulas:
$F = E-V+1+component $, and $ans=F-1$. All 1-vertex components are dropped off. They don't affect the number $F$.

5. How about vertices? Playing go, not chess!

6. Thanks to comment by @sxn91401 who gives good explanations.
`Vertex:` One of two endpoints of a slash/backslash, or a corner of a cell if the corner is on the border of the grid.
`Edge:` Every slash/backslash is an edge and connects two vertexes of the two endpoints. Also, a side of a cell is an edge if the side is a part of the border of the grid.
`Component:` A collection of vertexes that are connected by edges.
7. The UnionFind is using Size optimization which is fast.
8. The 2nd approach using DFS which is slower than implementation by UnionFind, but can be coded in a much shorter form.
# Real RUN for some testcases
grid=`["/\\/\\", "\\/\\/", "/\\/\\", "\\/\\\\"]`
```
V=21, E=32, component=1, F=13
 -----
|/\/\|
|\/\/|
|/\/\|
|\/\\|
 -----
```
grid=`["   ", " / ", "   "]`
```
V=14, E=13, component=2, F=2
 ----
|   |
| / |
|   |
 ----
```
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
Union find: $$O(\alpha(n^2)n^2)$$ where $\alpha(\cdot)$ is the inverse Ackermann function.
DFS :$O(n^2)$
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$$O(n^2)$$
# Code||0ms Beats 100%
```
// union find class with size
class UnionFind {
    vector<int> root, Size;
public:
    int merge;
    UnionFind(int N) : root(N), Size(N, 1), merge(0) {
        iota(root.begin(), root.end(), 0);
    }

    int Find(int x) {
        if (x == root[x])
            return x;
        return root[x] = Find(root[x]); // Path compression
    }

    bool Union(int x, int y) {
        x = Find(x), y = Find(y);

        if (x == y) return 0;

        if (Size[x] > Size[y]) {
            Size[x] += Size[y];
            root[y] = x;
        } else {
            Size[y] += Size[x];
            root[x] = y;
        }
        merge++;
        return 1;
    }
};

class Solution {
public:
    int regionsBySlashes(vector<string>& grid) {
        const int n = grid.size();
        const int side = n+1; // side length of the extended grid
        const int N = side*side; // total vertices in the extended grid

        bitset<962> vertex = 0; // Supports up to a 31x31 grid
        UnionFind G(N);

        int N0 = N-side;
        vertex[0] = 1;         // Top-left corner
        vertex[N0] = 1;        // Bottom-left corner

        for (int i = 0; i < n; i++) {
            vertex[i+1] = 1;               // Top border
            G.Union(i, i+1);

            vertex[i+N0+1] = 1;          // Bottom border
            G.Union(i+N0, i+N0+1);

            vertex[i*side] = 1;            // Left border
            G.Union(i*side, i*side+side);

            vertex[n+i*side] = 1;        // Right border
            G.Union(n+i*side, n+(i+1)*side);
        }

        int E = 4*n; // Initial edges from the borders

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '\\') {
                    int u = i*side + j;
                    int v = (i+1) * side + j + 1;
                    vertex[u] = 1, vertex[v] = 1;
                    G.Union(u, v);
                    E++;
                } 
                else if (grid[i][j] == '/') {
                    int u = i*side + j + 1;
                    int v = (i+1) * side + j;
                    vertex[u] = 1, vertex[v] = 1;
                    G.Union(u, v);
                    E++;
                }
            }
        }

        int V = vertex.count();
        int component = max(1, V - G.merge);
        int F = E-V + 1 + component;

        // output
        //cout<< "V="<<V<<", E="<<E<<", component="<<component<<", F="<<F<< endl;
        
        return F - 1; // Final face count
    }
};




auto init = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 'c';
}();
```
# C++ using DFS+Euler Theorem||4ms Beats 84.82%
```
class Solution {
public:
    static void dfs(int v, vector<vector<int>>& adj, bitset<962>& viz) {
        viz[v] = 1;
        for (int w : adj[v]) {
            if (viz[w]) continue;
            dfs(w, adj, viz);
        }
    }
    static int regionsBySlashes(vector<string>& grid) {
        const int n = grid.size();
        const int side = n+1; // side length of the extended grid
        const int N = side*side; // total vertices in the extended grid

        bitset<962> viz = 0; // Supports up to a 31x31 grid
        vector<vector<int>> adj(N);

        int N0 = N-side;
        for (int i = 0; i < n; i++) {
            adj[i].push_back(i+1);             // Top border
            adj[i+1].push_back(i);

            adj[i+N0].push_back(i+N0+1);   // Bottom border
            adj[i+N0+1].push_back(i+N0);

            adj[i*side].push_back((i+1)*side);    // Left border
            adj[(i+1)*side].push_back(i*side);

            adj[n+i*side].push_back(n+(i+1)*side); // Right border
            adj[n+(i+1)*side].push_back(n+i*side);
        }

        int E = 4*n; // Initial edges from the borders

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '\\') {
                    int u = i*side+j;
                    int v = (i+1)*side+j+1;
                    adj[u].push_back(v);
                    adj[v].push_back(u);
                    E++;
                } 
                else if (grid[i][j] == '/') {
                    int u = i*side+j+1;
                    int v = (i+1)*side+j;
                    adj[u].push_back(v);
                    adj[v].push_back(u);
                    E++;
                }
            }
        }

        int component = 0;
        for (int i=0; i < N; i++)
            // don't count isolated 1-vertex components
            if (!adj[i].empty() && !viz[i]) {
            //    cout << "\nStarting DFS for component at vertex: "<<i<<endl;
                component++;
                dfs(i, adj, viz);
            }
        
        int V = viz.count();
        int F = E-V+1+component;
        
        // output
       // cout<<"V="<<V<<", E="<<E<<", component="<<component<<", F="<<F<< endl;
        //print(grid);
        return F - 1; // Final face count
    }
};

```
['Math', 'Depth-First Search', 'Union Find', 'Graph', 'Matrix', 'C++']