Sharing my C++ solution


  • 0
    T
    class Solution {
    private:
        vector<int> graph;
        
        int find(int x)
        {
            if(x==graph[x])
                return x;
            else
                return find(graph[x]);
        }
        
    public:
        vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
            graph.resize(m*n);
            int i, j;
            for(i=0; i<m; i++)
                for(j=0; j<n; j++)
                    graph[i*n+j] = i*n+j;
            
            vector<int> result;
            int count=0;
            vector<vector<bool>> visited(m, vector<bool>(n, false));
            int direction[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };        
            int x, y, nextX, nextY, current, next;
            for(i=0; i<positions.size(); i++)
            {
                x = positions[i].first;
                y = positions[i].second;
                if(visited[x][y])
                    continue;
                    
                visited[x][y] = true;
                count++;
                current = x*n+y;
                for(j=0; j<4; j++)
                {
                    nextX = x + direction[j][0];
                    nextY = y + direction[j][1];
                    next = nextX*n+nextY;
                    if(nextX>=0 && nextX<m && nextY>=0 && nextY<n && visited[nextX][nextY] && find(next) != current)
                    {
                        graph[find(next)] = current;
                        count--;
                    }
                }
                
                result.push_back(count);
            }
            
            return result;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.