You are viewing a single comment's thread. Return to all comments →
I seem to be the only one using the Union Find algorithm:
#include <stdio.h> #include <stdlib.h> typedef struct { size_t *branches; size_t num_branches; } forest_t; forest_t new_forest(size_t max_num_trees) { forest_t forest = {.branches = (size_t *)malloc(max_num_trees * sizeof(size_t)), .num_branches = max_num_trees}; for (size_t i = 0; i < max_num_trees; i++) forest.branches[i] = i; return forest; } size_t find_root(const forest_t forest, size_t node_index) { while (forest.branches[node_index] != node_index) { node_index = forest.branches[node_index]; } return node_index; } void connect_trees(forest_t forest, size_t left_node, size_t right_node) { left_node = find_root(forest, left_node); right_node = find_root(forest, right_node); forest.branches[right_node] = left_node; } void free_forest(forest_t forest) { free(forest.branches); } size_t max(size_t left, size_t right) { return left > right ? left : right; } int main() { size_t num_rows; size_t num_columns; scanf("%lu", &num_rows); scanf("%lu", &num_columns); char *grid = (char *)malloc(num_rows * num_columns + 1); { for (size_t i = 0; i < num_rows; i++) { for (size_t j = 0; j < num_columns; j++) { int c; scanf("%d", &c); grid[i * num_columns + j] = c+'0'; } } } forest_t forest = new_forest(num_rows * num_columns); for (size_t i = 0; i < num_rows * num_columns; i++) { ssize_t row = i / num_columns; ssize_t col = i % num_columns; for (size_t k = 0; k < 8; k++) { size_t j = (k + 6) % 9; ssize_t row_neighbor = row + (ssize_t)(j / 3) - 1; ssize_t col_neighbor = col + (ssize_t)(j % 3) - 1; size_t l = row_neighbor * num_columns + col_neighbor; if (row_neighbor >= 0 && row_neighbor < num_rows && col_neighbor >= 0 && col_neighbor < num_columns && grid[i] == grid[l] && find_root(forest, i) != find_root(forest, l)) { connect_trees(forest, i, l); } } } size_t *root_counts = (size_t *)calloc(num_rows * num_columns, sizeof(size_t)); for (size_t i = 0; i < num_rows * num_columns; i++) { if (grid[i] == '1') { root_counts[find_root(forest, i)]++; } } size_t max_count = 0; for (size_t i = 0; i < num_rows * num_columns; i++) { max_count = max(max_count, root_counts[i]); } printf("%lu\n", max_count); }
Seems like cookies are disabled on this browser, please enable them to open this website
I agree to HackerRank's Terms of Service and Privacy Policy.
Connected Cells in a Grid
You are viewing a single comment's thread. Return to all comments →
I seem to be the only one using the Union Find algorithm: