LeetCode 200. Number of Islands

NumberOfIslands.c

int findTop(int *flag, int i) {
    while (flag[i] != i) i = flag[i];
    return i;
}

void mergeSet(int *flag, int i, int j) {
    int x = findTop(flag, i);
    int y = findTop(flag, j);
    flag[x] = y;
}

int numIslands(char** grid, int gridRowSize, int gridColSize) {
    int total = gridRowSize * gridColSize;
    if (total == 0) return 0;

    int *flag = (int *)malloc(total * sizeof(int));
    for (int i = 0; i < total; ++i) flag[i] = i;

    for (int i = 0; i < gridRowSize; ++i) {
        for (int j = 0; j < gridColSize; ++j) {
            int c = i * gridColSize + j;
            if (grid[i][j] == '0') {
                flag[c] = -1;
                continue;
            }

            if (j + 1 < gridColSize && grid[i][j + 1] == '1') {
                mergeSet(flag, i * gridColSize + j + 1, c);
            }
            if (i + 1 < gridRowSize && grid[i + 1][j] == '1') {
                mergeSet(flag, (i + 1) * gridColSize + j, c);
            }
        }
    }

    int res = 0;
    for (int i = 0; i < total; ++i)
        if (flag[i] == i) ++ res;

    free(flag);
    return res;
}