1. 문제 소개

3607. Power Grid Maintenance

2. 나의 풀이법

잘 모르겠어서 답지를 보며 풀었다.

class Solution:
    def processQueries(self, c: int, connections: List[List[int]], queries: List[List[int]]) -> List[int]:
        parent = list(range(c + 1))

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        for a, b in connections:
            ra, rb = find(a), find(b)
            if ra != rb:
                parent[rb] = ra

        next_node = [0] * (c + 1)
        comp_min = [0] * (c + 1)
        last: dict[int, int] = {}

        for i in range(1, c + 1):
            r = find(i)
            if comp_min[r] == 0:
                comp_min[r] = i
            else:
                next_node[last[r]] = i
            last[r] = i

        offline = [False] * (c + 1)
        ans: List[int] = []

        for t, x in queries:
            if t == 1:
                if not offline[x]:
                    ans.append(x)
                else:
                    r = find(x)
                    ans.append(comp_min[r] if comp_min[r] else -1)
            else:
                if not offline[x]:
                    offline[x] = True
                    r = find(x)
                    if comp_min[r] == x:
                        y = next_node[x]
                        while y and offline[y]:
                            y = next_node[y]
                        comp_min[r] = y if y else 0

        return ans

3. 다른 풀이법

heap을 사용한 풀이도 존재한다.

from collections import defaultdict
import heapq

class DSU:
    def __init__(self, n):
        self.parent = list(range(n + 1))

    def find(self, x):
        if self.parent[x] != x: self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return False
        self.parent[py] = px
        return True

class Solution:
    def processQueries(self, n: int, connections: List[List[int]], queries: List[List[int]]) -> List[int]:
        dsu = DSU(n)
        online = [True] * (n + 1)

        for u, v in connections: dsu.union(u, v)

        component_heap = defaultdict(list)
        for station in range(1, n + 1):
            root = dsu.find(station)
            heapq.heappush(component_heap[root], station)

        result = []

        for typ, x in queries:
            if typ == 2:
                online[x] = False
            else:
                if online[x]:
                    result.append(x)
                else:
                    root = dsu.find(x)
                    heap = component_heap[root]
                    while heap and not online[heap[0]]:
                        heapq.heappop(heap)
                    result.append(heap[0] if heap else -1)

        return result

4. 결론

요즘은 문제가 어렵다...