Count Servers that Communicate

Leetcode Problem:

• Count Servers that Communicate

Summary

• Counting servers that communicate with each other in a grid.

Approach

• This solution uses a breadth-first search (BFS) approach to traverse the grid and identify servers that can communicate with each other
• It uses a queue to keep track of nodes to visit and marks visited nodes to avoid revisiting them.

Complexity

• O(M*N + M*N) = O(2*M*N) due to the BFS traversal and marking of visited nodes.

Explanation

• The solution iterates over each cell in the grid
• If a cell contains a server (grid[i][j] == 1), it marks the cell as visited by setting it to 0 and adds it to a queue
• It then performs a BFS traversal, marking all connected servers as visited by setting them to 0
• The number of connected servers is stored in the variable 'cnt'
• If 'cnt' is greater than or equal to 2, it increments the 'ans' variable to count the servers that can communicate with each other.

Solution Code:

struct _node{
    int r;
    int c;
};
class Solution {
public:
    int countServers(vector>& grid) {
        int ans = 0;
        int M = grid.size();
        int N = grid[0].size();
        for(int i = 0 ; i < M; i++){
            for(int j = 0 ; j < N ;j++){
                queue<_node> que;
                if(grid[i][j]){
                    que.push({i, j});
                    grid[i][j] = 0;
                    int cnt = 1;
                    while(!que.empty()){
                        _node nod = que.front();
                        que.pop();
                        for(int k = 0 ; k < N; k++){
                            if(grid[nod.r][k]){
                                que.push({nod.r, k});
                                grid[nod.r][k] = 0;
                                cnt++;
                            }
                        }
                        for(int k = 0 ; k < M; k++){
                            if(grid[k][nod.c]){
                                que.push({k, nod.c});
                                grid[k][nod.c] = 0;
                                cnt++;
                            }
                        }
                    }
                    if(cnt >= 2) ans += cnt;
                }
            }
        }
        return ans;
    }
};