- Give each element a component representative.
- Merge representatives when a connection is accepted.
- Answer connectivity or component queries from the compressed representatives.
Code notes
- 86 lines of Python from the credited upstream file abc276_e.py.
- The implementation visibly relies on sequence storage, ordered lookup.
- No explicit loop blocks detected.
Complexity
Account for every find and union operation; with path compression and ranked merging, the amortized cost is nearly constant per operation.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
12 3 4class UnionFind:5 def __init__(self, number_count: int):6 self.parent_numbers = [-1 for _ in range(number_count)]7 8 def find_root(self, number: int) -> int:9 if self.parent_numbers[number] < 0:10 return number11 12 self.parent_numbers[number] = self.find_root(self.parent_numbers[number])13 return self.parent_numbers[number]14 15 def merge_if_needs(self, number_x: int, number_y: int) -> bool:16 x = self.find_root(number_x)17 y = self.find_root(number_y)18 19 if x == y:20 return False21 22 if self.parent_numbers[x] > self.parent_numbers[y]:23 x, y = y, x24 25 self.parent_numbers[x] += self.parent_numbers[y]26 self.parent_numbers[y] = x27 return True28 29 30def main():31 import sys32 33 input = sys.stdin.readline34 35 h, w = map(int, input().split())36 s = [list(input().rstrip()) for _ in range(h)]37 n = h * w + 138 uf = UnionFind(n)39 40 def to_id(i, j):41 return i * w + j42 43 44 45 sx, sy = -1, -146 47 for i in range(h):48 for j in range(w):49 if s[i][j] == "S":50 sx, sy = j, i51 52 if s[i][j] != ".":53 continue54 55 56 if (i + 1 < h) and s[i + 1][j] == ".":57 uf.merge_if_needs(to_id(i, j), to_id(i + 1, j))58 if (j + 1 < w) and s[i][j + 1] == ".":59 uf.merge_if_needs(to_id(i, j), to_id(i, j + 1))60 61 62 dxy = [(-1, 0), (1, 0), (0, -1), (0, 1)]63 count, leaders = 0, set()64 65 for dx, dy in dxy:66 nx, ny = sx + dx, sy + dy67 68 if ny < 0 or ny >= h:69 continue70 if nx < 0 or nx >= w:71 continue72 if s[ny][nx] == "#":73 continue74 75 leaders.add(uf.find_root(to_id(ny, nx)))76 count += 177 78 if len(leaders) == count:79 print("No")80 else:81 print("Yes")82 83 84if __name__ == "__main__":85 main()86