Buggy python submission (verdict: Time Limit Exceeded):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1 for _ in range(n)]  # 各要素の親 自分が根の場合は -1 * (木の要素数)

    def root(self, x):  # xが属する木の根を返す
        if self.parents[x] < 0:  # 自分が根の場合
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def merge(self, x, y):  # xが属する木とyが属する木を合体する
        x_root = self.root(x)  # xの根
        y_root = self.root(y)  # yの根

        if x_root == y_root:  # 同じ木に属する
            return

        if self.parents[x_root] > self.parents[y_root]:  # x_rootの要素数 > y_rootの要素数 にする
            x_root, y_root = y_root, x_root

        self.parents[x_root] += self.parents[y_root]
        self.parents[y_root] = x_root

    def size(self, x):  # xが属する木の要素数
        return -self.parents[self.root(x)]

    def same(self, x, y):  # xとyが同じ木に属するか判定
        return self.root(x) == self.root(y)

    def roots(self):  # すべての根を求める
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):  # 木が何個あるか
        return len(self.roots())

    def members(self, x):  # xが属する木の要素を列挙
        x_root = self.root(x)
        return [i for i in range(self.n) if self.root(i) == x_root]

    def all_group_members(self):  # すべての根の要素を列挙
        return {root: self.members(root) for root in self.roots()}


def main():
    h, w = map(int, input().split())
    grid = [list(input()) for _ in range(h)]
    uf = UnionFind(h * w)

    for r in range(h):
        for c in range(w):
            for dr, dc in [[0, 1], [1, 0]]:
                nr = r + dr
                nc = c + dc
                if not (0 <= nr < h and 0 <= nc < w):
                    continue
                if grid[r][c] != grid[nr][nc]:
                    uf.merge(r * w + c, nr * w + nc)

    ans = 0
    for tree in list(uf.all_group_members().values()):
        black, white = 0, 0
        for num in tree:
            if grid[num // w][num % w] == "#":
                black += 1
            else:
                white += 1
        ans += black * white

    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1 for _ in range(n)]  # 各要素の親 自分が根の場合は -1 * (木の要素数)

    def root(self, x):  # xが属する木の根を返す
        if self.parents[x] < 0:  # 自分が根の場合
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def merge(self, x, y):  # xが属する木とyが属する木を合体する
        x_root = self.root(x)  # xの根
        y_root = self.root(y)  # yの根

        if x_root == y_root:  # 同じ木に属する
            return

        if self.parents[x_root] > self.parents[y_root]:  # x_rootの要素数 > y_rootの要素数 にする
            x_root, y_root = y_root, x_root

        self.parents[x_root] += self.parents[y_root]
        self.parents[y_root] = x_root


def main():
    h, w = map(int, input().split())
    grid = [list(input()) for _ in range(h)]
    black_list = []
    uf = UnionFind(h * w)

    for r in range(h):
        for c in range(w):
            if grid[r][c] == "#":
                black_list.append([r, c])
            for dr, dc in [[0, 1], [1, 0]]:
                nr = r + dr
                nc = c + dc
                if not (0 <= nr < h and 0 <= nc < w):
                    continue
                if grid[r][c] != grid[nr][nc]:
                    uf.merge(r * w + c, nr * w + nc)

    ans = 0
    black_dict = dict()
    for r, c in black_list:
        z = uf.root(r * w + c)
        if z in black_dict:
            black_dict[z] += 1
        else:
            black_dict[z] = 1

    for index, num in enumerate(uf.parents):
        if num < 0:
            if index not in black_dict:
                continue
            ans += black_dict[index] * (- num - black_dict[index])

    print(ans)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1 for _ in range(n)]  # 各要素の親 自分が根の場合は -1 * (木の要素数)

    def root(self, x):  # xが属する木の根を返す
        if self.parents[x] < 0:  # 自分が根の場合
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def merge(self, x, y):  # xが属する木とyが属する木を合体する
        x_root = self.root(x)  # xの根
        y_root = self.root(y)  # yの根

        if x_root == y_root:  # 同じ木に属する
            return

        if abs(self.parents[x_root]) >= abs(self.parents[y_root]):  # 要素数の比較
            self.parents[x_root] += self.parents[y_root]
            self.parents[y_root] = x_root
        else:
            self.parents[y_root] += self.parents[x_root]
            self.parents[x_root] = y_root

    def size(self, x):  # xが属する木の要素数
        return -self.parents[self.root(x)]

    def same(self, x, y):  # xとyが同じ木に属するか判定
        return self.root(x) == self.root(y)

    def roots(self):  # すべての根を求める
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):  # 木が何個あるか
        return len(self.roots())

    def members(self, x):  # xが属する木の要素を列挙
        x_root = self.root(x)
        return [i for i in range(self.n) if self.root(i) == x_root]

    def all_group_members(self):  # すべての根の要素を列挙
        return {root: self.members(root) for root in self.roots()}


def main():
    h, w = map(int, input().split())
    s_list = [list(input()) for _ in range(h)]
    num_list = [0 for _ in range(h * w)]
    for i in range(h):
        for j in range(w):
            if s_list[i][j] == "#":
                num_list[i * w + j] = "#"
            else:
                num_list[i * w + j] = "."
    uf = UnionFind(h * w)

    for r in range(h):
        for c in range(w):
            nc = c + 1
            nr = r + 1
            if s_list[r][c] == "#":
                if nc < w and s_list[r][nc] == ".":
                    uf.merge(r * w + c, r * w + nc)
                if nr < h and s_list[nr][c] == ".":
                    uf.merge(r * w + c, nr * w + c)
            else:
                if nc < w and s_list[r][nc] == "#":
                    uf.merge(r * w + c, r * w + nc)
                if nr < h and s_list[nr][c] == "#":
                    uf.merge(r * w + c, nr * w + c)

    ans = 0
    for tree in list(uf.all_group_members().values()):
        cnt1 = 0
        cnt2 = 0
        for num in tree:
            if num_list[num] == "#":
                cnt1 += 1
            else:
                cnt2 += 1
        ans += cnt1 * cnt2

    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1 for _ in range(n)]  # 各要素の親 自分が根の場合は -1 * (木の要素数)

    def root(self, x):  # xが属する木の根を返す
        if self.parents[x] < 0:  # 自分が根の場合
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def merge(self, x, y):  # xが属する木とyが属する木を合体する
        x_root = self.root(x)  # xの根
        y_root = self.root(y)  # yの根

        if x_root == y_root:  # 同じ木に属する
            return

        if self.parents[x_root] > self.parents[y_root]:  # x_rootの要素数 > y_rootの要素数 にする
            x_root, y_root = y_root, x_root

        self.parents[x_root] += self.parents[y_root]
        self.parents[y_root] = x_root


def main():
    h, w = map(int, input().split())
    grid = [list(input()) for _ in range(h)]
    black_list = []
    uf = UnionFind(h * w)

    for r in range(h):
        for c in range(w):
            if grid[r][c] == "#":
                black_list.append([r, c])
            for dr, dc in [[0, 1], [1, 0]]:
                nr = r + dr
                nc = c + dc
                if not (0 <= nr < h and 0 <= nc < w):
                    continue
                if grid[r][c] != grid[nr][nc]:
                    uf.merge(r * w + c, nr * w + nc)

    ans = 0
    black_dict = dict()
    for r, c in black_list:
        z = uf.root(r * w + c)
        if z in black_dict:
            black_dict[z] += 1
        else:
            black_dict[z] = 1

    for index, num in enumerate(uf.parents):
        if num < 0:
            if index not in black_dict:
                continue
            ans += black_dict[index] * (- num - black_dict[index])

    print(ans)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1 for _ in range(n)]  # 各要素の親 自分が根の場合は -1 * (木の要素数)

    def root(self, x):  # xが属する木の根を返す
        if self.parents[x] < 0:  # 自分が根の場合
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def merge(self, x, y):  # xが属する木とyが属する木を合体する
        x_root = self.root(x)  # xの根
        y_root = self.root(y)  # yの根

        if x_root == y_root:  # 同じ木に属する
            return

        if abs(self.parents[x_root]) >= abs(self.parents[y_root]):  # 要素数の比較
            self.parents[x_root] += self.parents[y_root]
            self.parents[y_root] = x_root
        else:
            self.parents[y_root] += self.parents[x_root]
            self.parents[x_root] = y_root

    def size(self, x):  # xが属する木の要素数
        return -self.parents[self.root(x)]

    def same(self, x, y):  # xとyが同じ木に属するか判定
        return self.root(x) == self.root(y)

    def roots(self):  # すべての根を求める
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):  # 木が何個あるか
        return len(self.roots())

    def members(self, x):  # xが属する木の要素を列挙
        x_root = self.root(x)
        return [i for i in range(self.n) if self.root(i) == x_root]

    def all_group_members(self):  # すべての根の要素を列挙
        return {root: self.members(root) for root in self.roots()}


def main():
    h, w = map(int, input().split())
    s_list = [list(input()) for _ in range(h)]
    uf = UnionFind(h * w)

    for r in range(h):
        for c in range(w):
            if s_list[r][c] == "#":
                if c + 1 < w:
                    if s_list[r][c + 1] == ".":
                        uf.merge(r * w + c, r * w + c + 1)
                if r + 1 < h:
                    if s_list[r + 1][c] == ".":
                        uf.merge(r * w + c, (r + 1) * w + c)
            elif s_list[r][c] == ".":
                if c + 1 < w:
                    if s_list[r][c + 1] == "#":
                        uf.merge(r * w + c, r * w + c + 1)
                if r + 1 < h:
                    if s_list[r + 1][c] == "#":
                        uf.merge(r * w + c, (r + 1) * w + c)

    ans = 0
    # for i in range(uf.group_count()):
    #     cnt1 = 0
    #     cnt2 = 0
    #     for num in list(uf.all_group_members().values())[i]:
    #         if s_list[num // w][num % w] == "#":
    #             cnt1 += 1
    #         else:
    #             cnt2 += 1
    #     ans += cnt1 * cnt2

    # print(ans)

    for tree in list(uf.all_group_members().values()):
        cnt1 = 0
        cnt2 = 0
        for num in tree:
            if s_list[num // w][num % w] == "#":
                cnt1 += 1
            else:
                cnt2 += 1
        ans += cnt1 * cnt2

    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1 for _ in range(n)]  # 各要素の親 自分が根の場合は -1 * (木の要素数)

    def root(self, x):  # xが属する木の根を返す
        if self.parents[x] < 0:  # 自分が根の場合
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def merge(self, x, y):  # xが属する木とyが属する木を合体する
        x_root = self.root(x)  # xの根
        y_root = self.root(y)  # yの根

        if x_root == y_root:  # 同じ木に属する
            return

        if self.parents[x_root] > self.parents[y_root]:  # x_rootの要素数 > y_rootの要素数 にする
            x_root, y_root = y_root, x_root

        self.parents[x_root] += self.parents[y_root]
        self.parents[y_root] = x_root


def main():
    h, w = map(int, input().split())
    grid = [list(input()) for _ in range(h)]
    black_list = []
    uf = UnionFind(h * w)

    for r in range(h):
        for c in range(w):
            if grid[r][c] == "#":
                black_list.append([r, c])
            for dr, dc in [[0, 1], [1, 0]]:
                nr = r + dr
                nc = c + dc
                if not (0 <= nr < h and 0 <= nc < w):
                    continue
                if grid[r][c] != grid[nr][nc]:
                    uf.merge(r * w + c, nr * w + nc)

    ans = 0
    black_dict = dict()
    for r, c in black_list:
        z = uf.root(r * w + c)
        if z in black_dict:
            black_dict[z] += 1
        else:
            black_dict[z] = 1

    for index, num in enumerate(uf.parents):
        if num < 0:
            if index not in black_dict:
                continue
            ans += black_dict[index] * (- num - black_dict[index])

    print(ans)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1 for _ in range(n)]  # 各要素の親 自分が根の場合は -1 * (木の要素数)

    def root(self, x):  # xが属する木の根を返す
        if self.parents[x] < 0:  # 自分が根の場合
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def merge(self, x, y):  # xが属する木とyが属する木を合体する
        x_root = self.root(x)  # xの根
        y_root = self.root(y)  # yの根

        if x_root == y_root:  # 同じ木に属する
            return

        if abs(self.parents[x_root]) >= abs(self.parents[y_root]):  # 要素数の比較
            self.parents[x_root] += self.parents[y_root]
            self.parents[y_root] = x_root
        else:
            self.parents[y_root] += self.parents[x_root]
            self.parents[x_root] = y_root

    def size(self, x):  # xが属する木の要素数
        return -self.parents[self.root(x)]

    def same(self, x, y):  # xとyが同じ木に属するか判定
        return self.root(x) == self.root(y)

    def roots(self):  # すべての根を求める
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):  # 木が何個あるか
        return len(self.roots())

    def members(self, x):  # xが属する木の要素を列挙
        x_root = self.root(x)
        return [i for i in range(self.n) if self.root(i) == x_root]

    def all_group_members(self):  # すべての根の要素を列挙
        return {root: self.members(root) for root in self.roots()}


def main():
    h, w = map(int, input().split())
    s_list = [list(input()) for _ in range(h)]
    num_list = [[0 for _ in range(w)] for _ in range(h)]
    for i in range(h):
        for j in range(w):
            num_list[i][j] = i * w + j

    uf = UnionFind(h * w)

    for r in range(h):
        for c in range(w):
            if s_list[r][c] == "#":
                if c + 1 < w:
                    if s_list[r][c + 1] == ".":
                        uf.merge(num_list[r][c], num_list[r][c + 1])
                if r + 1 < h:
                    if s_list[r + 1][c] == ".":
                        uf.merge(num_list[r][c], num_list[r + 1][c])
            if s_list[r][c] == ".":
                if c + 1 < w:
                    if s_list[r][c + 1] == "#":
                        uf.merge(num_list[r][c], num_list[r][c + 1])
                if r + 1 < h:
                    if s_list[r + 1][c] == "#":
                        uf.merge(num_list[r][c], num_list[r + 1][c])

    ans = 0
    for i in range(uf.group_count()):
        cnt1 = 0
        cnt2 = 0
        for num in list(uf.all_group_members().values())[i]:
            if s_list[num // w][num % w] == "#":
                cnt1 += 1
            else:
                cnt2 += 1
        ans += cnt1 * cnt2

    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1 for _ in range(n)]  # 各要素の親 自分が根の場合は -1 * (木の要素数)

    def root(self, x):  # xが属する木の根を返す
        if self.parents[x] < 0:  # 自分が根の場合
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def merge(self, x, y):  # xが属する木とyが属する木を合体する
        x_root = self.root(x)  # xの根
        y_root = self.root(y)  # yの根

        if x_root == y_root:  # 同じ木に属する
            return

        if self.parents[x_root] > self.parents[y_root]:  # x_rootの要素数 > y_rootの要素数 にする
            x_root, y_root = y_root, x_root

        self.parents[x_root] += self.parents[y_root]
        self.parents[y_root] = x_root


def main():
    h, w = map(int, input().split())
    grid = [list(input()) for _ in range(h)]
    black_list = []
    uf = UnionFind(h * w)

    for r in range(h):
        for c in range(w):
            if grid[r][c] == "#":
                black_list.append([r, c])
            for dr, dc in [[0, 1], [1, 0]]:
                nr = r + dr
                nc = c + dc
                if not (0 <= nr < h and 0 <= nc < w):
                    continue
                if grid[r][c] != grid[nr][nc]:
                    uf.merge(r * w + c, nr * w + nc)

    ans = 0
    black_dict = dict()
    for r, c in black_list:
        z = uf.root(r * w + c)
        if z in black_dict:
            black_dict[z] += 1
        else:
            black_dict[z] = 1

    for index, num in enumerate(uf.parents):
        if num < 0:
            if index not in black_dict:
                continue
            ans += black_dict[index] * (- num - black_dict[index])

    print(ans)


if __name__ == "__main__":
    main()