Leetcode 1559: Detect Cycles in 2D Grid

 https://leetcode.com/problems/detect-cycles-in-2d-grid/description/

Notes:

This question belongs to find the connected groups. One way is that we can use union-find, (or bfs, or dfs).

One of the features about the circle is that: each element on the circle has at least 2 neighbors with the same letter. So the in-degree is 2 or larger.

This can give us a way to solve this problem: 

1): we can label all the elements with in-degree less than 2 to be invalid. 

2): then we can just perform "find island" with the elements with in-degree >= 2 only;

3): if there is any "island" or connected group having a size larger > 3, return true;

4): o/w, return false; 

So step 1) is the key. One difficulty is that: say there is one element has an in-degree larger than 1, but if one or more of its neighbors (with the same letter) only has an in-degree of 1, then the in-degree of the element will be decreased by removing the invalid neighbors.

We can apply bfs to gradually label all the elements as invalid. The logic here is similar to topology sort: we will start with elements with in-degree of 1. Then gradually search its four neighbors:

1): if the neighbor is not the same letter, continue;

2): else if the neighbor has a positive in-degree, then update it by minus 1;

After handling all the four neighbors, we need to scan the four neighbor again to see the final in-degrees. If the in-degree is 1, we will push it to the bfs queue; o/w, continue (if < 1, this element has no effect on others; if >1, still belongs to valid group).

After finishing this step, all the remaining elements with in-degree > 2 will be the pool to forme "islands" or connected groups. If any of the island has a size larger than 3, return true; o/w, return false.

Here use the union-find algorithm for finding circles.  

See the code below:

class Solution {
struct UF {
    vector<int> ps, cts;
    int num, mx;
    UF(int n): ps(n, 0), cts(n, 1), num(n), mx(0) {
        iota(ps.begin(), ps.end(), 0);
        if(n>0) mx = 1;
    }
    int find(int x) {
        if(ps[x] == x) return x;
        return ps[x] = find(ps[x]);
    }
    void unite (int x, int y) {
        int a = find(x), b = find(y);
        if(a != b) {
            ps[b] = a;
            cts[a] += cts[b];
            mx = max(mx, cts[a]);
            --num;
        }
    }
};
public:
    bool containsCycle(vector<vector<char>>& grid) {
        if(!grid.size() || !grid.front().size()) return false;
        int m = grid.size(), n = grid.front().size();
        vector<int> dirs = {-1, 0, 1, 0, -1};
        vector<vector<int>> ids(m, vector<int>(n, 0));
        queue<pair<int, int>> q;
        for(int i=0; i<m; ++i) {
            for(int j=0; j<n; ++j) {
                for(int k=0; k+1<dirs.size(); ++k) {
                    int a = i + dirs[k], b = j + dirs[k+1];
                    if(a<0 || a>=m || b<0 || b>=n || grid[a][b] != grid[i][j]) continue;
                    ++ids[i][j];
                }
                if(ids[i][j] == 1) q.push({i, j});
            }
        }
        while(q.size()) {
            auto t = q.front();
            q.pop();
            int x = t.first, y = t.second;
            --ids[x][y];
            for(int k=0; k+1<dirs.size(); ++k) {
                int a = x + dirs[k], b = y + dirs[k+1];
                if(a<0 || a>=m || b<0 || b>=n) continue;
                if(grid[a][b] == grid[x][y] && ids[a][b] > 0) --ids[a][b];
            }
            for(int k=0; k+1<dirs.size(); ++k) {
                int a = x + dirs[k], b = y + dirs[k+1];
                if(a<0 || a>=m || b<0 || b>=n || grid[a][b] != grid[x][y] || ids[a][b] != 1) continue;
                q.push({a, b});
            }
        }
        UF uf(m*n);
        for(int i=0; i<m; ++i) {
            for(int j=0; j<n; ++j) {
                if(ids[i][j] < 2) continue; 
                int a = i-1, b = j-1;
                // upper 
                if(a>=0 && grid[a][j] == grid[i][j] && ids[a][j] > 1) uf.unite(a*n+j, i*n+j);
                // left
                if(b>=0 && grid[i][b] == grid[i][j] && ids[i][b] > 1) uf.unite(i*n+b, i*n+j);
            }
        }
        return uf.mx > 3;
    }
};