問題
既存投稿一覧ページへのリンク
解法手順1
-
Union-Find木を初期化します。都市とは別に、全ての発電所を代表する仮想的なノードを1つ追加する。
-
クエリで切断されない電線について、Union-Find木で接続する。
-
クエリを逆順に処理する。
- 現在の状態で、発電所を代表するノードに接続されている都市の数を数えます。これが答えとなる。
- クエリで指定された電線を接続する（逆順なので、本来は切断する操作）。
-
全てのクエリの結果を出力する。
入力例01の可視化
-
初期状態
-
3番目の(5-10)の経路が遮断され、都市5が停電
-
5番目と8番目の(2-9)、(3-6)の経路が遮断され、都市2、都市3が停電
-
10番目と2番目と7番目の(1-8)、(4-10)、(1-7)の経路が遮断され、都市1が停電
ACコード1
ac.py
class UnionFind:
def __init__(self, n):
self.par = [-1] * n # 親ノードを格納するリスト。初期値は全て-1（自身が根）
def root(self, x):
if self.par[x] < 0: # xが根の場合
return x
self.par[x] = self.root(self.par[x]) # 経路圧縮
return self.par[x]
def unite(self, x, y):
rx, ry = self.root(x), self.root(y) # xとyの根を取得
if rx == ry: # 既に同じ木に属している場合
return
if -self.par[rx] < -self.par[ry]: # ryの方が大きい木の場合
rx, ry = ry, rx
self.par[rx] += self.par[ry] # rxにryを統合
self.par[ry] = rx
def size(self, x):
return -self.par[self.root(x)] # xが属する木のサイズを返す
def io_func():
N, _, E = map(int, input().split()) # 都市数、発電所数、電線数を入力
edges = [tuple(map(lambda x: min(N, int(x) - 1), input().split())) for _ in range(E)] # 電線の情報を入力
Q = int(input()) # クエリ数を入力
query = [int(input()) - 1 for _ in range(Q)] # クエリを入力
return N, E, edges, Q, query
def solve(N, E, edges, Q, query):
ans = [0] * Q # 答えを格納するリスト
uf = UnionFind(N + 1) # Union-Find木を初期化（都市 + 仮想ノード）
for i in set(range(E)) - set(query): # クエリで切断されない電線を接続
u, v = edges[i]
uf.unite(u, v)
for i in range(Q - 1, -1, -1): # クエリを逆順に処理
ans[i] = uf.size(N) - 1 # 発電所（仮想ノード）に接続されている都市数を計算
uf.unite(*edges[query[i]]) # クエリで指定された電線を接続
for res in ans: # 結果を出力
print(res)
# メイン処理
N, E, edges, Q, query = io_func() # 入力を受け取る
solve(N, E, edges, Q, query) # 問題を解く
###
# N: 都市の数
# E: 電線の数
# edges: 電線の接続情報を格納するリスト
# Q: クエリの数
# query: クエリの情報を格納するリスト
# ans: 各クエリに対する答えを格納するリスト
# uf: Union-Find木のインスタンス
# 1. UnionFind クラス:
# - __init__: Union-Find木を初期化
# - root: 要素の根を見つける（経路圧縮あり）
# - unite: 2つの要素を結合
# - size: 指定された要素が属する木のサイズを返す
# 2. io_func 関数:
# - 標準入力から問題の入力を受け取り、必要なデータ構造に変換
# 3. solve 関数:
# - Union-Find木を用いて問題を解く
# - クエリを逆順に処理し、各時点での電気の通っている都市数を計算
# - 結果を出力
# 4. メイン処理:
# - io_func で入力を受け取り
# - solve 関数を呼び出して問題を解く
オブジェクト指向版1(TLE)
ac_object.py
import logging
from abc import ABC, abstractmethod
def setup_logger(debug_mode):
logger = logging.getLogger(__name__)
if not logger.handlers: # ハンドラが存在しない場合のみ追加
logger.setLevel(logging.DEBUG if debug_mode else logging.INFO)
formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')
file_handler = logging.FileHandler('program_trace.log', encoding="utf8")
file_handler.setFormatter(formatter)
logger.addHandler(file_handler)
return logger
class UnionFind:
def __init__(self, n, debug_mode=False):
self.par = [-1] * n # 親ノードを格納するリスト。初期値は全て-1（自身が根）
self.logger = setup_logger(debug_mode)
def root(self, x):
if self.par[x] < 0: # xが根の場合
self.logger.debug(f"ノード {x} は根です")
return x
self.logger.debug(f"ノード {x} の親を探索中")
self.par[x] = self.root(self.par[x]) # 経路圧縮
self.logger.debug(f"ノード {x} の根は {self.par[x]} です")
return self.par[x]
def unite(self, x, y):
self.logger.debug(f"ノード {x} と {y} を結合します")
rx, ry = self.root(x), self.root(y) # xとyの根を取得
if rx == ry: # 既に同じ木に属している場合
self.logger.debug(f"ノード {x} と {y} は既に同じ木に属しています")
return
if -self.par[rx] < -self.par[ry]: # ryの方が大きい木の場合
rx, ry = ry, rx
self.par[rx] += self.par[ry] # rxにryを統合
self.par[ry] = rx
self.logger.debug(f"ノード {x} と {y} を結合しました。新しい根は {rx} です")
def size(self, x):
size = -self.par[self.root(x)] # xが属する木のサイズを返す
self.logger.debug(f"ノード {x} が属する木のサイズは {size} です")
return size
class InputHandler(ABC):
@abstractmethod
def get_input(self):
pass
class StandardInputHandler(InputHandler):
def get_input(self):
N, _, E = map(int, input().split()) # 都市数、発電所数、電線数を入力
# edges = [tuple(map(lambda x: min(N, int(x) - 1), input().split())) for _ in range(E)] # 電線の情報を入力
edges = []
for _ in range(E):
u, v = input().split()
u = min(N, int(u) - 1)
v = min(N, int(v) - 1)
edges.append((u, v))
Q = int(input()) # クエリ数を入力
query = [int(input()) - 1 for _ in range(Q)] # クエリを入力
return N, E, edges, Q, query
class OutputHandler(ABC):
@abstractmethod
def output_result(self, result):
pass
class StandardOutputHandler(OutputHandler):
def output_result(self, result):
for res in result:
print(res)
class ElectricityProblemSolver:
def __init__(self, input_handler: InputHandler, output_handler: OutputHandler, debug_mode=False):
self.input_handler = input_handler
self.output_handler = output_handler
self.debug_mode = debug_mode
self.logger = setup_logger(debug_mode)
def solve(self):
# 入力を受け取る
N, E, edges, Q, query = self.input_handler.get_input()
self.logger.debug(f"入力: N={N}, E={E}, Q={Q}")
self.logger.debug(f"入力: edges={edges}")
self.logger.debug(f"入力: query={query}")
# 問題を解く
ans = [0] * Q # 答えを格納するリスト
uf = UnionFind(N + 1, self.debug_mode) # Union-Find木を初期化（都市 + 仮想ノード）
self.logger.debug("クエリで切断されない電線を接続")
for i in set(range(E)) - set(query): # クエリで切断されない電線を接続
u, v = edges[i]
uf.unite(u, v)
self.logger.debug("クエリを逆順に処理")
for i in range(Q - 1, -1, -1): # クエリを逆順に処理
ans[i] = uf.size(N) - 1 # 発電所（仮想ノード）に接続されている都市数を計算
self.logger.debug(f"クエリ {Q-i}: 接続都市数 = {ans[i]}")
uf.unite(*edges[query[i]]) # クエリで指定された電線を接続
# 結果を出力
self.logger.debug("結果を出力")
self.output_handler.output_result(ans)
# メイン処理
if __name__ == "__main__":
input_handler = StandardInputHandler()
output_handler = StandardOutputHandler()
solver = ElectricityProblemSolver(input_handler, output_handler, debug_mode=True)
solver.solve()
オブジェクト図
