제출 #1098138

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1098138		vjudge1	다리 (APIO19_bridges)	Cpython 3	0 / 100	3060 ms	45592 KiB

bridges

class Bridges:
    def __init__(self, n, m):
        self.n = n
        self.m = m
        self.graph = [[] for _ in range(n+1)]
        self.weights = {}

    def add_bridge(self, u, v, w):
        self.graph[u].append(v)
        self.graph[v].append(u)
        self.weights[(u, v)] = w
        self.weights[(v, u)] = w

    def update_weight(self, bridge_id, new_weight):
        edges = list(self.weights.keys())
        if bridge_id <= len(edges):
            u, v = edges[bridge_id - 1]
            self.weights[(u, v)] = new_weight
            self.weights[(v, u)] = new_weight

    def reachable_islands(self, s):
        visited = [False] * (self.n + 1)
        self.dfs(s, visited)
        return visited.count(True)

    def dfs(self, node, visited):
        visited[node] = True
        for neighbor in self.graph[node]:
            if not visited[neighbor]:
                self.dfs(neighbor, visited)


n, m = map(int, input().split())
bridges = Bridges(n, m)
for _ in range(m):
    u, v, w = map(int, input().split())
    bridges.add_bridge(u, v, w)
q = int(input())
for _ in range(q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        _, bridge_id, new_weight = query
        bridges.update_weight(bridge_id, new_weight)
    elif query[0] == 2:
        _, s, t = query
        result = bridges.reachable_islands(s)
        print(result)

• Subtask 1: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27