Connected Sets

connected-sets.cpp

#include <iostream>
#include <vector>

using namespace std;

typedef vector<vector<bool>> Matrix;
int current_matrix_size = 0;

bool is_valid(Matrix& m, int i, int j)
{
    return i < current_matrix_size && i >= 0 && j < current_matrix_size && j >= 0 && m[i][j];
}

int find_connected_set(Matrix& m, int i, int j)
{
    m[i][j] = false;
    
    if(is_valid(m, i-1, j-1))
    {
        find_connected_set(m, i-1, j-1);
    }
    if(is_valid(m, i, j-1))
    {
        find_connected_set(m, i, j-1);
    }
    if(is_valid(m, i+1, j-1))
    {
        find_connected_set(m, i+1, j-1);
    }
    if(is_valid(m, i-1, j))
    {
        find_connected_set(m, i-1, j);
    }
    if(is_valid(m, i+1, j))
    {
        find_connected_set(m, i+1, j);
    }
    if(is_valid(m, i-1, j+1))
    {
        find_connected_set(m, i-1, j+1);
    }
    if(is_valid(m, i, j+1))
    {
        find_connected_set(m, i, j+1);
    }
    if(is_valid(m, i+1, j+1))
    {
        find_connected_set(m, i+1, j+1);
    }
    
    return 1;
}

int main()
{
    int number_of_tests;
    cin >> number_of_tests;
    
    for(int test_case = 0; test_case < number_of_tests; ++test_case)
    {
        int matrix_size;
        cin >> matrix_size;
        current_matrix_size = matrix_size;
        
        Matrix matrix(matrix_size, vector<bool>(matrix_size));
        
        for(int i = 0; i < matrix_size; ++i)
        {
            for(int j = 0; j < matrix_size; ++j)
            {
                int element;
                cin >> element;
                matrix[i][j] = static_cast<bool>(element);
            }
        }
        
        int connected_sets_count = 0;
        for(int i = 0; i < matrix_size; ++i)
        {
            for(int j = 0; j < matrix_size; ++j)
            {
                if(matrix[i][j])
                {
                    connected_sets_count += find_connected_set(matrix, i, j);
                }
            }
        }
        cout << connected_sets_count << endl;
        
    }
    
    return 0;
}